从特殊到一般
我们先看链的情况。
我们把点$1$左右的两条子链分别扔入堆里
每次取出两个堆的最大值，把答案累加上更大的那个（另一堆为空则直接加上去）。
那么......如果$1$连着多条链咋办？
我们又发现，你可以每次把每2条链所对的堆两两合并，并不影响答案。
那么......如果$1$连着多棵树咋办？
其实是链是树已经没多大区别了，因为它们之间互不影响。
于是做法就出来了
dfs把子树合并，一层层合并上去就好辣
注意为了保证复杂度$O(nlog^2n)$，我们要做启发式合并，就是每次把小的堆合并到大的堆上去
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; inline int Max(int a,int b){return a>b?a:b;} inline void Swap(int &a,int &b){a^=b^=a^=b;} void read(int &x){ char c=getchar();x=0; while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar(); } #define N 200005 int n,val[N],tp,tmp[N],id[N]; long long ans; int cnt,hd[N],nxt[N],ed[N],poi[N]; priority_queue <int> h[N]; inline void adde(int x,int y){ nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt, ed[x]=cnt, poi[cnt]=y; } void merge(int &x,int &y){ if(h[x].size()<h[y].size()) Swap(x,y);//启发式合并 while(!h[y].empty()){ tmp[++tp]=Max(h[x].top(),h[y].top()); h[x].pop(); h[y].pop(); } while(tp) h[x].push(tmp[tp--]); } void dfs(int x){ id[x]=x; for(int i=hd[x];i;i=nxt[i])dfs(poi[i]),merge(id[x],id[poi[i]]); h[id[x]].push(val[x]); } int main(){ read(n); for(int i=1;i<=n;++i) read(val[i]); for(int i=2,q;i<=n;++i) read(q),adde(q,i); dfs(1); while(!h[id[1]].empty()) ans+=h[id[1]].top(),h[id[1]].pop(); printf("%lld",ans); return 0; }