洛谷5290 [十二省联考2019]春节十二响

又看了一圈题，感觉只有这个和树有关的题貌似可以做。

然并卵，靠自己还是只有打暴力，甚至把链都推错了。我最开始认为链就是所有点之和，然后很开心的WA了。

看了题解才醒悟过来根节点 $1$ 不一定在链的端点，对于链应该对根节点两端建堆，然后贪心从两端各取一个取较大值计入答案。

正解就是对每个子树作链的操作，一遍dfs就出来了。

具体做法是对每个节点建堆，在回溯时对当前节点 $x$ 枚举所有子节点 $y$ ，将 $size$ 小的合并到大的上，合并后节点的dfs序也要对应取 $size$ 较大的dfs序。最后将根节点堆中元素全部加上即为答案。

下面代码用了emplace()，需要交C++11

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    ll next,to;
} edge[200005];
ll n,m,a,cnt,dfsord,head[200005],id[200005],siz[200005],nxt[200005],s[200005];
priority_queue <ll> q[200005];

inline void add(ll u,ll v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(ll x)
{
    id[x]=++dfsord;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        dfs(y);
        if (q[id[x]].size()<q[id[y]].size()) swap(id[x],id[y]);
        ll m=0;
        while (!q[id[y]].empty())
        {
            nxt[++m]=max(q[id[x]].top(),q[id[y]].top());
            q[id[x]].pop(); q[id[y]].pop();
        }
        for (ll i=1;i<=m;i++) q[id[x]].emplace(nxt[i]);
    }
    q[id[x]].emplace(s[x]);
}

int main()
{
    n=read();
    for (ll i=1;i<=n;i++) s[i]=read();
    for (ll i=2;i<=n;i++) add(read(),i);
    dfs(1);
    ll ans=0;
    while (!q[id[1]].empty()) 
    {
        ans+=q[id[1]].top();
        q[id[1]].pop();
    }
    printf("%lld",ans);
    return 0;
}