题目链接。
题意
给出一棵有 \(n\) 个节点的树，要求你将集合 \(\{1,2,\dots,n\}\) 划分成若干个子集，使得没有子集拥有节点对满足两个元素在树上是祖孙关系。你需要最小化子集的最大值之和。
先考虑带有启发性的子任务 \(4\)（树是一颗链）。具体来说，树有以下两种形态：
-
根节点是链的一个端点
答案显然为 \(\sum_{i=1}^nM_i\)。
-
根节点不是链的端点
此时树的形态：从根节点挂了两条链下去。
考虑对根的每颗子树维护一个堆，堆中存对于当前子树最小划分集合的方案（根据情况 \(1\)，\(\text{集合}=\{\forall M_i[i\in \text{subtree}]\}\)）。在根节点处合并两颗子树的堆：采用贪心的思想，我们优先合并两个堆中最大的元素，放入新堆里，并在原来的堆中删去……以此类推，直到某一个堆为空，再把非空堆中剩余的元素加入新堆即可。
根据这样的合并方法，我们不难推出 \(O(n^2)\) 的通用解法。
但显然，\(O(n^2)\) 过不了这题，所以我们可以把暴力合并集合的方式改成树上启发式合并。合并 \(s1,s2\) 的时候要格外注意写法，正确的合并复杂度应该是 \(\min(s1,s2)\)，不要让复杂度变成 \(\max(s1,s2)\)。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n; ll ans, a[N];
vector<int> e[N];
priority_queue<ll> now, q[N];
void merge(int u, int v){
if(q[u].size() < q[v].size())
q[u].swap(q[v]);
while(!q[v].empty()){
now.push(max(q[u].top(), q[v].top()));
q[u].pop(), q[v].pop();
}
while(!now.empty())
q[u].push(now.top()), now.pop();
}
void dfs(int u){
for(int &v: e[u])
dfs(v), merge(u, v);
q[u].push(a[u]);
}
int main(){
scanf("%d", &n);
FL(i, 1, n) scanf("%lld", &a[i]);
FL(i, 2, n){
int p; scanf("%d", &p);
e[p].emplace_back(i);
}
dfs(1);
while(!q[1].empty())
ans += q[1].top(), q[1].pop();
printf("%lld\n", ans);
return 0;
}