【十二省联考2019】春节十二响

题面

https://www.luogu.org/problem/P5290

题解

真的是我傻逼，十二省联考$day2$至今还是我的噩梦。$day1$起码一直在调可持久化$trie$树，$day2$真的是一道题都不会写啊。

皮配以为是生成函数，写了$20pts$暴力就放掉了。

春节十二响读错题意，想了半天没有想出来，甚至一条链的情况本来想出来排序的方法了，但是过了一会竟然忘掉了（可能是因为太紧张吧，脑子里面奇奇怪怪的不知道在想什么，可能在想我的女神吧），最后写了一个不知所云的线段树，我明明都看出来$T2$是最简单的一题了，但最后还是没做出来，唉。

最后对着希望看了一个半小时，放弃了。

回家之后重新想这道题，只需要对每一棵子树分别做，把一条链的情况拓展出来就可以了。窝写的$set$启发式合并。

现在想想，要是再遇到一样的绝望，我该怎么办呢？

#include <cstdio>
#include <iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
#define ri register int
#define N 200050
using namespace std;

int n,a[N];
vector<int> son[N];
int fa[N],fs[N];
multiset<int,greater<int>> s[N];
multiset<int,greater<int>>::iterator it1,it2;

void solve(int x) {
  if (son[x].size()==0) {
    fs[x]=x;
    s[x].insert(a[x]);
    return;
  }
  int maxs=0,yson=-1;
  for (ri i=0;i<son[x].size();i++) {
    solve(son[x][i]);
    if (s[fs[son[x][i]]].size()>maxs) maxs=s[fs[son[x][i]]].size(),yson=son[x][i];
  }
  fs[x]=fs[yson];
  int now=fs[x];
  for (ri i=0;i<son[x].size();i++) if (son[x][i] != yson) {
    for (it1=s[fs[son[x][i]]].begin(),it2=s[now].begin();it1!=s[fs[son[x][i]]].end();it1++,it2++) {
      if (*it1>*it2) s[now].erase(it2),s[now].insert(*it1);
    }
  }
  s[now].insert(a[x]);
  return;
}

int main() {
  scanf("%d", &n);
  for (ri i=1;i<=n;i++) scanf("%d", &a[i]);
  for (ri i=2;i<=n;i++) {
    scanf("%d",&fa[i]);
    son[fa[i]].push_back(i);
  }
  solve(1);
  long long ans=0;
  for (it1=s[fs[1]].begin();it1!=s[fs[1]].end();it1++) {
    ans+=*it1;
  }
  cout<<ans<<endl;
}