LG5290/LOJ3052 春节十二响 题解(启发式合并)

作者：XiaoQuQu，发表于 Mon Feb 26 2024。

考虑当这个东西是一条链的时候我们该怎么做，显然 $1$​ 会有两个儿子，然后两个儿子分别是一条链。

所以我们可以给两个儿子的链上的所有节点分别加到两个堆里，每次取出两个堆的最大值加入到我们选择的答案中，然后把两个堆的最大值全部 pop 掉。最终的答案就是我们 pop 完一个堆之后，所有 pop 出来的元素与另一个堆中没有 pop 出来的元素之和，最终再加上 $a_1$。

考虑这个东西为啥是对的。假设正解与我们存在差异，设我们选择的与正解选择的第一次出现不一样时，我们选择的 $x$，而正解选择的 $y$。由于我们每次必定选择最大值，所以必定有 $a_x>a_y$。且考虑由于我们之前的选择每次都是弹出两个（其中小的将与大的合并），所以将不会有剩余的段可以给 $a_x$ 放入。于是我们 $a_x$ 必定需要新开一个段，所以答案必定更劣。

然后这玩意扩展到树上正确性也是显然的，可以对树高归纳证得。

然后发现一个问题，我们需要将一个堆 pop 到空，最差情况是 $O((\max size_u) \times size_x)$ 的（其中我们遍历到 $x$ 且 $x$ 是 $u$ 的父亲），考虑这玩意能怎么优化，显然在树上的时候，我们并不关心单个子树的答案，我们只关心这个子树在我们合并完之后，他的堆长啥样。所以我们考虑启发式合并，将 size 小的合并到 size 大的里面，于是就可以在 $O(\sum size_u)$ 的时间内做完这个了。

最后时间复杂度 $O(n\log n)$。

const int MAXN = 2e5 + 5;
int n, f[MAXN], a[MAXN];
priority_queue<int> pq[MAXN];
vector<int> G[MAXN];

void dfs(int x, int fa) {
	vector<int> v;
	for (auto u:G[x]) {
		if (u == fa) continue;
		dfs(u, x);
		if (pq[u].size() > pq[x].size()) swap(pq[x], pq[u]);
		while (pq[x].size() && pq[u].size()) {
			const int mx = max(pq[u].top(), pq[x].top());
			v.push_back(mx);
			pq[u].pop(); pq[x].pop();
		}
		while (v.size()) {
			pq[x].push(v.back());
			v.pop_back();
		}
	}
	pq[x].push(a[x]);
}

void work() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 2; i <= n; ++i) {
		cin >> f[i];
		G[f[i]].push_back(i);
	}
	dfs(1, 0);
	int ans = 0;
	while (pq[1].size()) ans += pq[1].top(), pq[1].pop();
	cout << ans << endl;
}