P5290 [十二省联考2019]春节十二响（堆+启发式合并）

P5290 [十二省联考2019]春节十二响

从特殊到一般

我们先看链的情况。

我们把点$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 ;

}

巴特西

P5290 [十二省联考2019]春节十二响（堆+启发式合并）

最新文章

热门文章