从特殊到一般
我们先看链的情况。
我们把点$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=;
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') x=x*+(c^),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=;i<=n;++i) read(val[i]);
for(int i=,q;i<=n;++i) read(q),adde(q,i);
dfs();
while(!h[id[]].empty()) ans+=h[id[]].top(),h[id[]].pop();
printf("%lld",ans);
return ;
}