自动搬运

查看原文

来自洛谷，原作者为

	Loser_Syx 不可逆の方が美しいから

搬运于2025-08-24 22:55:02，当前版本为作者最后更新于2024-02-06 09:42:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我们考虑最小的遍历次数如何得来，应该是要每个节点都被访问过且遍历链的次数最少，那么我们就应该要让链最长，显然是需要一口气遍历一个最长的链，也就是到叶子结点，那么最小遍历次数应为叶子结点个数。

因为最小遍历次数是叶子节点个数，所以只有 $p_1 \sim p_{cnt}$ 对答案有效，$cnt$ 为叶子结点个数。

因为每个叶子节点只会被遍历到一次，所以不妨初始时将叶子节点视为一个可行方案进行 dp。
具体地，按深度由深到浅的顺序进行 dp，每次将当前节点的方案数转移给它的父亲，这个是每个父亲所拥有的叶子节点个数（被遍历到的次数）。

我们再来考虑如何得到答案，首先记录 $p_1 \sim p_{cnt}$ 的药水会生成在哪里，然后在 dp 过程中求解。
因为我们是按照深度从深到浅 dp 的，所以如果当前 $i$ 有剩余的没有遍历过的叶子节点，且 $i$ 会生成药水，那么我们就可以领取 $i$ 上部分的药水（越多越好），不过方案数也要减去对应数量，所以我们 dp 转移的并非叶子结点个数，而是剩余没有遍历到过的叶子结点个数。
不妨想想为什么是对的，因为当前节点 $i$ 的子树被遍历过了（深度原因），而我们的 $i$ 的子树内，一定是不能再获得药水了的情况，而如果我们不拿 $i$ 的药水或是不最大化拿的数量的话，可能会导致 $i$ 的祖先的某个节点，方案数多于其药水数，而不能达到最大化的效果。

至此，复杂度 $O(n)$，可以通过。

const int N=1e5+19;
int p[N], cnt[N], dep[N], tot, mx, f[N], fa[N];
vector<int> g[N], depid[N];
void dfs(int u, int fat) {
	dep[u] = dep[fat]+1;
	fa[u] = fat;
	mx = max(dep[u], mx);
	depid[dep[u]].emplace_back(u);
	bool flg=0;
	for (const int i : g[u]) {
		if (i != fat) dfs(i, u), flg=1;
	}
	if (!flg) {
		tot++; f[u]++; 
	}
}
signed main() {
	int n = read();
	for (int i=1;i<=n;++i) read(p[i]);
	for (int i=1;i<n;++i) {
		int a, b; read(a, b);
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	dfs(1, 1);
	for (int i=1;i<=tot;++i) cnt[p[i]]++;
	int ans=0;
	while (mx) {
		for (const int i : depid[mx]) {
			if (f[i]) {
				if (cnt[i] <= f[i]) f[i] -= cnt[i], ans += cnt[i];
				else ans += f[i], f[i] = 0;
			}
			f[fa[i]] += f[i];
		}
		--mx;
	}
	write(ans, '\n');
	return 0;
}