题目链接：LOJ 3052

距离苏拉威西只有一百公里了，车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉芬面前的屏幕，那是控制行星发动机的关键程序：春节十二响。他需要将其部署到电力控制系统的一个芯片中。

「春节十二响」由 $n$ 个子程序构成，第 $i$ 个子程序所需的内存空间是 $M_i$。这 $n$ 个子程序之间的调用关系构成了一棵以第 $1$ 个子程序为根的树，其中第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。

由于内存紧张，电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干个段 $S_1, S_2, \dots, S_k$，并将每个程序预先分配到一个固定的段。如果两个子程序没有直接或间接的调用关系，则他们可以被分配到同一个段中，反之则不能。换言之，当且仅当 $a$ 和 $b$ 在调用树上不是祖先-后代关系，$a$ 和 $b$ 可以被分配到同一个段中。

一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值，所有段大小的和不能超过系统的内存大小。

现在艾莉芬想要知道，电力控制芯片至少要有多少内存，才能保证春节十二响的正确运行。即：最少需要多大的内存，才能通过先将内存分成若干个段，再把每个子程序分配到一个段中，使得每个段中分配的所有子程序之间不存在祖先-后代关系。

数据范围：$1 \le n \le 2 \times 10 ^ 5$，$1 \le M_i \le 10 ^ 9$。

Solution

我们对每个点维护一个优先队列，对于节点 $u$ 的若干儿子 $v$，由于这些 $v$ 之间没有祖先-后代关系，于是我们可以将他们的值直接合并到 $u$。很显然 $u$ 位置的值为：所有 $v$ 对应位置的最大值，加上 $u$ 本身的内存值。

考虑这样合并的复杂度是错误的，每个点的优先队列大小等于其向下最深的链的长度，这和长链剖分非常类似，于是我们每次把小的合并到大的里面，这和启发式合并又非常相似了。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <cstdio>
#include <algorithm>
#include <queue>

const int N = 2e5 + 5, M = 4e5 + 5;

int n, tot, a[N], tmp[N], lnk[N], ter[M], nxt[M];
std::priority_queue<int> pq[N];

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
void dfs(int u, int p) {
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        dfs(v, u);
        if (pq[u].size() < pq[v].size()) std::swap(pq[u], pq[v]);
        int m = pq[v].size();
        for (int i = 1; i <= m; i++) {
            tmp[i] = std::max(pq[u].top(), pq[v].top());
            pq[u].pop(), pq[v].pop();
        }
        for (int i = 1; i <= m; i++) pq[u].push(tmp[i]);
    }
    pq[u].push(a[u]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 2; i <= n; i++) {
        int f;
        scanf("%d", &f);
        add(i, f), add(f, i);
    }
    dfs(1, 0);
    long long ans = 0;
    while (!pq[1].empty()) ans += pq[1].top(), pq[1].pop();
    printf("%lld\n", ans);
    return 0;
}