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

感觉作为例题还是挺不错的。

感官上直接分析比较困难。不妨先考虑怎样的段长集合是合法的。

注意到合法等价于对每一条从根到叶子的链都合法，考虑在链上贪心，尝试将每个和比他大的最小的点做匹配，如果能匹配上就是合法。很显然，如果仅考虑一条链，那么极小的一个合法段长集合就是这条链的点权集合。这启发我们考虑将每一条这样的根到叶子的链的答案合并，每次贪心取两者最大值即可。这样就获得了一个 \(O(n^2\log n)\) 的做法。

考虑优化这个过程，首先每条链的对应集合可以放到 DFS 的过程中去做，但是这样做不了。利用 dp 的思想，记 \(S_u\) 表示以 \(u\) 为根的子树对应的集合，那么每次转移合并子树即可。注意到合并的复杂度和深度有关，那么来个长链剖分就变成线性的了。算上堆的复杂度就是 \(O(n \log n)\)。

const int N = 2e5 + 10;
int n, a[N];
vector<int> G[N];

int dep[N];
priority_queue<int> s[N];

void dfs(int u) {
  int t = 0;
  for(int v : G[u]) {
    dfs(v);
    if(dep[v] > dep[t]) t = v;
  }
  dep[u] = dep[t] + 1;
  swap(s[u], s[t]);
  for(int v : G[u]) {
    if(v == t) continue;
    vector<int> buf;
    for(int k = 1; k <= dep[v]; ++k) {
      int w = s[v].top(); s[v].pop();
      int c = s[u].top(); s[u].pop();
      buf.emplace_back(max(w, c));
    }
    for(int x : buf) s[u].push(x);
  }
  s[u].push(a[u]);
}

int main() {
  read(n);
  for(int i = 1; i <= n; ++i)
    read(a[i]);
  for(int i = 2; i <= n; ++i) {
    int x; read(x);
    G[x].emplace_back(i);
  }
  dfs(1);
  LL ans = 0;
  while(s[1].size()) {
    ans += s[1].top();
    s[1].pop();
  }
  printf("%lld\n",ans);
}