zcmimi's blog
查看原题

点击跳转

题目的意思就是相同子树中的点不能分配到同一段内存

每个点都开一个大根堆

合并一个点和它的子节点的时候最大值互相对应

启发式合并

具体看代码

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define Fur(i,x,y) for(int i(x);i<=y;++i)
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IO;
const int N=200011;
int n,cnt=0,head[N],a[N],id[N],dfn=0,tmp[N],tp=0;
struct edge{int to,nxt;}e[N];
il void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
std::priority_queue<int>q[N];
il int max(int x,int y){return x>y?x:y;}
il void swap(int &x,int &y){int t=x;x=y;y=t;}
void dfs(int x){
    id[x]=++dfn;
    for(int i(head[x]),to;to=e[i].to,i;i=e[i].nxt){
        dfs(to);
        if(q[id[x]].size()<q[id[to]].size())swap(id[x],id[to]);
        int t=q[id[to]].size();tp=0;
        while(t--)
            tmp[++tp]=max(q[id[x]].top(),q[id[to]].top()),
            q[id[x]].pop(),q[id[to]].pop();
        while(tp)q[id[x]].push(tmp[tp--]);
    }
    q[id[x]].push(a[x]);
}
int main(){
    in(n);
    int x;
    Fur(i,1,n)in(a[i]);
    Fur(i,2,n)in(x),add(x,i);
    dfs(1);
    long long ans=0;
    while(!q[id[1]].empty())
        ans+=q[id[1]].top(),
        q[id[1]].pop();
    printf("%lld\n",ans);
}
LG 5290 [十二省联考2019]春节十二响
comment评论
Search
search