题目大意
给定一棵 $n$ 个结点的树，每个结点有权值 $M_i$。要求将树上的节点分组，每组的结点中的任意两个不是祖先 - 后代关系。一组的代价为包含的节点的权值的最大值，一个方案的代价是每组的代价之和，求最小代价。
数据范围：$n \le 2 \times 10^5$。
思路分析
非常巧妙的一道题。
首先考虑一条链，答案就是两个支链权值分别从大到小排序然后对应位置取最大值加起来。
链的部分分可以提示正解就是一个合并的过程。对于每个点维护一个大根堆，每次将儿子一一合并到自己上面，合并的方式是对应位置取最大值。合并完所有儿子后将自己的权值加入堆中就行了。
注意到暴力合并复杂度不能接受，只能启发式合并。因为每合并一次元素会减少一个，所以总共合并 $n$ 次，再加上堆的复杂度，总时间复杂度 $O(n \log n)$。
代码实现
代码虽短，实现还是需要一些技巧的。具体见代码。
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | const int maxn = 2e5; |
6 | int n, a[maxn + 3], f[maxn + 3], id[maxn + 3], k, t[maxn + 3]; |
7 | priority_queue<int> H[maxn + 3]; |
8 | |
9 | int main() { |
10 | scanf("%d", &n); |
11 | for (int i = 1; i <= n; i++) scanf("%d", &a[i]); |
12 | for (int i = 2; i <= n; i++) scanf("%d", &f[i]); |
13 | for (int i = n; i > 1; i--) { |
14 | if (!id[i]) id[i] = i; |
15 | H[id[i]].push(a[i]); |
16 | if (!id[f[i]]) { |
17 | id[f[i]] = id[i]; |
18 | continue; |
19 | } |
20 | if (H[id[f[i]]].size() < H[id[i]].size()) { |
21 | swap(id[i], id[f[i]]); |
22 | } |
23 | while (H[id[i]].size()) { |
24 | t[++k] = max(H[id[i]].top(), H[id[f[i]]].top()); |
25 | H[id[i]].pop(), H[id[f[i]]].pop(); |
26 | } |
27 | do { |
28 | H[id[f[i]]].push(t[k]); |
29 | } while (--k); |
30 | } |
31 | long long ans = a[1]; |
32 | while (H[id[1]].size()) { |
33 | ans += H[id[1]].top(), H[id[1]].pop(); |
34 | } |
35 | printf("%lld\n", ans); |
36 | return 0; |
37 | } |