十二省联考2019 春节十二响

题目连接：戳我

我们读完题之后简单演算一下，会发现一个贪心——就是每个结点的子链上面一一向比自己大的配对即可。

这样的话我们可以对于每个节点都开一个大根堆，然后一一合并。

但是时间复杂度是过不去的。所以我们考虑启发式合并。

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#define MAXN 200010
using namespace std;
int n,t,tot;
int fa[MAXN],a[MAXN],head[MAXN],siz[MAXN],tmp[MAXN],id[MAXN];
long long ans;
priority_queue<int>q[MAXN];
struct Edge{int nxt,to,dis;}edge[MAXN<<1];
inline void add(int from,int to){edge[++t].nxt=head[from],edge[t].to=to,head[from]=t;}
inline void solve(int x)
{
    id[x]=++tot;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int now=edge[i].to;
        solve(now);
        if(q[id[x]].size()<q[id[now]].size()) swap(id[x],id[now]);
        int cnt=q[id[now]].size();
        for(int i=1;i<=cnt;i++) 
            tmp[i]=max(q[id[x]].top(),q[id[now]].top()),q[id[x]].pop(),q[id[now]].pop();
        for(int i=1;i<=cnt;i++) q[id[x]].push(tmp[i]);
    }
    q[id[x]].push(a[x]);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=2;i<=n;i++) scanf("%d",&fa[i]),add(fa[i],i);
    solve(1);
    while(!q[id[1]].empty())
        ans+=q[id[1]].top(),q[id[1]].pop();
    printf("%lld
",ans);
    return 0;
}