题目大意
- 给一棵树，点有点权，要求把所有节点分成若干个集合，使得同一集合中任意两点不存在祖先关系，且每一集合的最大点权的和最小
题解
- 考虑递归处理，假设当前节点的两棵子树都已处理好，那么合并两棵子树的方式为最大值和最大值合并，次大值和次大值合并
- 可以用长链剖分+优先队列来优化到O(nlogn)
代码
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 const int N=200010; 7 int n,tot,cnt,sz,a[N],head[N],id[N],son[N],deep[N],tmp[N]; 8 struct edge{int to,from;}e[N]; 9 priority_queue<int>Q[N]; 10 long long ans; 11 void insert(int x,int y){ e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt; } 12 void pre(int x) 13 { 14 deep[x]=1; 15 for (int i=head[x];i;i=e[i].from) pre(e[i].to),deep[x]=max(deep[x],deep[e[i].to]+1); 16 for (int i=head[x];i;i=e[i].from) if (deep[x]==deep[e[i].to]+1) son[x]=e[i].to; 17 } 18 void dfs(int x) 19 { 20 if (son[x]) dfs(son[x]),id[x]=id[son[x]]; 21 for (int i=head[x];i;i=e[i].from) 22 if (e[i].to!=son[x]) 23 { 24 dfs(e[i].to),tot=0; 25 while (!Q[id[e[i].to]].empty()) tmp[++tot]=max(Q[id[x]].top(),Q[id[e[i].to]].top()),Q[id[x]].pop(),Q[id[e[i].to]].pop(); 26 while (tot) Q[id[x]].push(tmp[tot]),tot--; 27 } 28 if (!id[x]) id[x]=++sz; 29 Q[id[x]].push(a[x]); 30 } 31 int main() 32 { 33 scanf("%d",&n); 34 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 35 for (int i=2,x;i<=n;i++) scanf("%d",&x),insert(x,i); 36 pre(1),dfs(1); 37 while (!Q[id[1]].empty()) ans+=Q[id[1]].top(),Q[id[1]].pop(); 38 printf("%lld",ans); 39 }