自动搬运

查看原文

来自洛谷，原作者为

	liuyz11 这个家伙很懒，而且还很菜

搬运于2025-08-24 21:50:20，当前版本为作者最后更新于2020-07-10 10:23:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先对于指定的那条边，可以把它拆成两棵树或者建一个0的点与这两点相连.

会想到计算每个叶子节点的每组蚂蚁到指定边后还剩多少蚂蚁，显然会超时.

我们倒过来考虑，从指定的边开始计算.

假设第 $i$ 个节点存在数量大于等于 $dp1_i$ 的蚂蚁，且小于等于 $dp2_i$的蚂蚁最终到达指定边会被吃掉(即恰好 $k$ 只).

容易得到转移方程:

$dp1_v = dp1_u \cdot (c_u - 1)$

$dp2_v = (dp2_u + 1) \cdot (c_u - 1) - 1$

其中 $c_u$ 表示点 $u$ 的度

一开始 $dp1_0$ 与 $dp2_0$都为k.

最后对于每一个叶子结点 $i$，在 $m$ 数组中二分查找大于等于 $dp1_i$ 且小于等于 $dp2_i$ 的数量.

参考代码

#include <bits/stdc++.h>
#define rep(x, l, r) for(int x = l; x <= r; x++)
using namespace std;
typedef long long ll;

const ll INF = 1 << 30;
const int MAXN = 1e7 + 5;

int n, m, k, cnt, root1, root2;
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1];
int a[MAXN];
ll dp1[MAXN], dp2[MAXN], c[MAXN];

void addedge(int u, int v){
	cnt++;
	nxt[cnt] = head[u];
	head[u] = cnt;
	to[cnt] = v;
}

void add(int u, int v){
	addedge(u, v);
	addedge(v, u);
	c[u]++; c[v]++;
}

void dfs(int u, int fa){
	for(int e = head[u]; e; e = nxt[e]){
		int v = to[e];
		if(v == fa) continue;
		dp1[v] = min(INF, dp1[u] * (c[u] - 1));//防止炸longlong
		dp2[v] = min(INF, (dp2[u] + 1) * (c[u] - 1) - 1); 
		dfs(v, u);
	}
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	rep(i, 1, m) scanf("%d", &a[i]);
	sort(a + 1, a + m + 1);
	scanf("%d%d", &root1, &root2);
	add(0, root1);//建一个0点与两个根节点连边
	add(0, root2);
	rep(i, 1, n - 2){
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y);
	}
	dp1[0] = dp2[0] = k;
	dfs(0, -1);
	ll ans = 0;
	rep(i, 1, n)
		if(c[i] == 1){
			ans += upper_bound(a + 1, a + m + 1, dp2[i]) - lower_bound(a + 1, a + m + 1, dp1[i]);
		}
	printf("%lld\n", ans * k);//最后记得要乘上k
	return 0;
}