Luogu5290 十二省联考2019春节十二响（贪心+启发式合并）

时间：2021-03-20 04:30:45

　　考虑链的做法，显然将两部分各自从大到小排序后逐位取max即可，最后将根计入。猜想树上做法相同，即按上述方式逐个合并子树，最后加入根。用multiset启发式合并即可维护。因为每次合并后较小集合会消失，总复杂度O(nlogn)。场上并没有被启发得到这个优美的贪心。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;

#define ll long long

#define N 200010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

    int x=0,f=1;char c=getchar();

    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

int n,a[N],b[N],p[N],fa[N],size[N],t;

ll ans;

struct data{int to,nxt;

}edge[N];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

multiset<int> q[N];

void dfs(int k,int from)

{

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from)

    {

        dfs(edge[i].to,k);

        if (size[k]<size[edge[i].to]) swap(q[k],q[edge[i].to]);

        auto it=q[edge[i].to].end(),it2=q[k].end();

        int cnt=0;

        while (!q[edge[i].to].empty())

        {

            it--,it2--;

            b[++cnt]=max(*it,*it2);

            it=q[edge[i].to].erase(it);

            it2=q[k].erase(it2);

        }

        for (int j=1;j<=cnt;j++) q[k].insert(b[j]);

        size[k]=max(size[k],size[edge[i].to]);

    }

    size[k]++;q[k].insert(a[k]);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=1;i<=n;i++) a[i]=read();

    for (int i=2;i<=n;i++)

    {

        fa[i]=read();

        addedge(fa[i],i);

    }

    dfs(1,1);

    for (auto i:q[1]) ans+=i;

    cout<<ans;

    return 0;

}

　　

相关文章