LibreOJ 3052 「十二省联考 2019」春节十二响

有思维难度，其实挺好写的。

首先，考虑一条链的情况。
那么根节点最多有两个儿子，分别延伸出两条链。
当且仅当在这两条链中各选择一个点（除了根节点），才不会有祖孙关系。
所以可以贪心地上两个堆。

考虑 100% 的数据，那么这个时候就涉及到堆的合并。
于是我们启发式合并。

这个时候，时间复杂度不再是 O(nlog2n) 了。
因为合并的时候，更大的那个，大小应该是其对应子树中的最长链长度。
根据长链剖分的分析，得到 O(nlogn)。

还有，
pbds 天 下 第 一！

代码：

#include <cstdio>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int N = 2e5;
int n,a[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
long long ans;
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
__gnu_pbds::priority_queue<int> q[N + 5];
int id[N + 5];
int merge(int x,int y)
{
    static int buf[N + 5];
    if(q[id[x]].size() < q[id[y]].size())
        swap(id[x],id[y]);
    int m = q[id[y]].size();
    for(register int i = 1;i <= m;++i)
        buf[i] = max(q[id[x]].top(),q[id[y]].top()),q[id[x]].pop(),q[id[y]].pop();
    for(register int i = 1;i <= m;++i)
        q[id[x]].push(buf[i]);
    return id[x];
}
void dfs(int p,int fa)
{
    static int tot = 0;
    id[p] = ++tot;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa)
            dfs(to[i],p),id[p] = merge(p,to[i]);
    q[id[p]].push(a[p]);
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    int u;
    for(register int i = 2;i <= n;++i)
        scanf("%d",&u),add(u,i);
    dfs(1,0);
    for(;!q[id[1]].empty();q[id[1]].pop())
        ans += q[id[1]].top();
    printf("%lld\n",ans);
}