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

传送门

Description

将\(N\)个节点的树分成若干个节点的集合，其中每个集合不包含"祖先——后代关系“

每个集合的代价是集合内最大的点权，最小化代价和

Solution

启发式合并

对于合并两个子树的集合，开个\(pq\)，每次把最大的两个合并，代价更新为两个集合的最大值

Code?

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define reg register
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

const int MN=2e5+5;
struct edge{int to,nex;}e[MN<<1];
int hr[MN],en;
inline void ins(int x,int y){e[++en]=(edge){y,hr[x]};hr[x]=en;}
int n,M[MN],p[MN];
ll ans;
std::priority_queue<ll> s[MN];

void dfs(int x)
{
    static int st[MN],top;
    
    p[x]=x;reg int i,j;
    
    for(i=hr[x];i;i=e[i].nex)
    {
        dfs(e[i].to);
        if(i==hr[x]) p[x]=p[e[i].to];
        else
        {
            if(s[p[x]].size()<s[p[e[i].to]].size()) std::swap(p[x],p[e[i].to]);
            
            top=0;
            while(!s[p[e[i].to]].empty())
                st[++top]=max(s[p[e[i].to]].top(),s[p[x]].top()),s[p[x]].pop(),s[p[e[i].to]].pop();
            
            while(top) s[p[x]].push(st[top--]);
        }
    }
    
    s[p[x]].push(M[x]);
}
int main()
{
    n=read();reg int i;
    for(i=1;i<=n;++i) M[i]=read();
    for(i=2;i<=n;++i) ins(read(),i);
    
    dfs(1);
    while(!s[p[1]].empty()) ans+=s[p[1]].top(),s[p[1]].pop();
    
    printf("%lld\n",ans);
    return 0;
}

Blog来自PaperCloud，未经允许，请勿转载，TKS！