题解 P5290 【[十二省联考2019]春节十二响】

· · 题解

启发式合并并不是O(nlog^2n),而是O(nlogn)。

  做法：由链的部分分可以发现，对于一条链可以直接对于左右各开一个堆，然后每次左右各弹一个取max,我们思考怎么由链拓宽到树上。

  以二叉树为例，它的每一个二叉可以看做一条链，左右两部分按照部分分的方式合并之后就变成了条新的链，链上每个点为之前两条“子链”的两个对应点的max,然后递归的做下去就好了。

  至于多叉树，显然和二叉树一样。

时间复杂度

  发下来的solution以及楼上的题解中都有提到，认为它是log^2,但是请注意，这道题和传统的启发式合并并不一样，因为它并没有“合并”进去，而是把小的那部分“贴”上去后直接把小的“丢掉了”，每个点只会被遍历一次，而每弹出一个点是log的，所以总时间复杂度是O(nlogn)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
static char buf[100000],*pa,*pd;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
} 
const int N=1100000;
struct edge{
    int to,next;
}e[N];
int head[N],tot;
void add(int x,int y){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
} 
#define ll long long 
ll ans,val[N];
int n,po[N];
priority_queue<ll> son[N];
ll now[N];
int cnt;
void dfs(int u){
    po[u]=u;
    for(int i=head[u];i;i=e[i].next){
        dfs(e[i].to);
        if(i==head[u]){
            po[u]=po[e[i].to];
        } 
        else{
            if(son[po[u]].size()<son[po[e[i].to]].size())swap(po[u],po[e[i].to]);
            cnt=0;
            while(!son[po[e[i].to]].empty()){
                now[++cnt]=max(son[po[e[i].to]].top(),son[po[u]].top());son[po[u]].pop();son[po[e[i].to]].pop();
            }
            for(int j=1;j<=cnt;j++)
                son[po[u]].push(now[j]);
        } 
    }
    son[po[u]].push(val[u]);
} 
int main(){
    freopen("spring.in","r",stdin);
    freopen("spring.out","w",stdout);
    n=read();
    register int i;
    for(i=1;i<=n;i++)val[i]=read();
    for(i=2;i<=n;i++){
        int fa=read();add(fa,i);
    } 
    dfs(1);
    while(!son[po[1]].empty()){
        ans+=son[po[1]].top();son[po[1]].pop();
    }
    cout<<ans;
    return 0;
}