luogu P5290 [十二省联考2019]春节十二响 优先队列 + 启发式合并
思维难度不大，在考上上写的启发式合并写错了，只拿了 60 pts，好难过QAQ
没什么太难的，在考场上想出链的部分分之后很容易就能想到正解.
没错，就是非常短的启发式合并.
注意一下，写的要漂亮一点，否则会疯狂 TLE.
还有一个细节，想交换优先队列时不能直接交换队列，而是对于树中每个节点都存一个在实际队列编号中的位置，计为 $idx[u]$，每次交换 $idx[u]$ 和 $idx[to[v]]$.
Code:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#define maxn 200001
#define setIO(s) freopen(s".in","r",stdin) ,freopen(s".out","w",stdout)
using namespace std;
priority_queue<int>Q[maxn];
int edges;
int n;
int head[maxn],to[maxn],nex[maxn],val[maxn],f[maxn];
void addedge(int u,int v){
nex[++edges] = head[u], head[u] = edges, to[edges] = v;
}
int tmp[maxn];
int id[maxn]; int idx;
void DFS(int u){
id[u]=++idx;
for(int v=head[u];v;v=nex[v]){
DFS(to[v]);
if(Q[id[u]].size() < Q[id[to[v]]].size()) swap(id[u],id[to[v]]);
int m=Q[id[to[v]]].size();
for(int i=1;i<=m;++i) {
tmp[i]=max(Q[id[u]].top(),Q[id[to[v]]].top());
Q[id[u]].pop(); Q[id[to[v]]].pop();
}
for(int i=1;i<=m;++i) Q[id[u]].push(tmp[i]);
}
Q[id[u]].push(val[u]);
}
int main(){
//setIO("spring");
scanf("%d",&n);
for(int i = 1;i <= n; ++i) scanf("%d",&val[i]);
for(int i = 2;i <= n; ++i) scanf("%d",&f[i]);
for(int i = 2;i <= n; ++i) addedge(f[i],i);
DFS(1);
long long ans = 0;
while(!Q[id[1]].empty())ans += (long long)Q[id[1]].top(), Q[id[1]].pop();
printf("%lld
",ans);
return 0;
}