把你骨灰都给你扬了！

真是送分题…可惜因为心态原因考场上想出来正解了都没敢写..

首先考虑链的情况怎么做？

既然根不是链的端点，那么这条链一定分为两部分，把两部分的所有权值扔堆里，每次各拿出来两部分的最大值进行配对，然后扔到结果里。

最后加起来即可。

推广到树上呢？

很自然的想到写个DFS，这个DFS返回一个堆，表示这棵子树的答案。

然后对于一个点把他的子节点的堆拿出来每次取出所有的最大值合并

这样也是正确的，可惜时间复杂度和空间复杂度都可以被卡到$O(n^2)$。

怎么优化呢?考虑到一个到子树内叶子节点最远距离为x的点，堆里只会有x个取值。

所以我们可以长链剖分。

对于一个点，我们优先递归它的深子节点，然后把其他的子节点的答案合并到这个深子节点的堆上。

具体实现就是对于一条长链顶，我们新建一个堆，然后这条长链都使用这一个堆。

当从长链顶返回时，合并完答案后，删除这个堆即可。

时间复杂度为所有长链长度之和乘上堆的复杂度，即$O(nlogn)$。

#include <assert.h>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

using heap_t = std::multiset<int_t, std::greater<int_t>>;

const int_t LARGE = 2e5;
int_t maxChd[LARGE + 1], depth[LARGE + 1], maxDepth[LARGE + 1];
int_t vals[LARGE + 1];
int_t n;
std::vector<int_t> graph[LARGE + 1];

void DFS1(int_t vtx) {
    maxDepth[vtx] = depth[vtx];
    for (int_t to : graph[vtx]) {
        depth[to] = depth[vtx] + 1;
        DFS1(to);
        maxDepth[vtx] = std::max(maxDepth[vtx], maxDepth[to]);
    }
    for (int_t to : graph[vtx]) {
        if (maxDepth[to] > maxDepth[maxChd[vtx]]) {
            maxChd[vtx] = to;
        }
    }
    if (maxChd[vtx] == vtx) maxChd[vtx] = 0;
}
void DFS2(int_t vtx, heap_t* heap) {
    //先递归重子节点
    if (maxChd[vtx]) DFS2(maxChd[vtx], heap);
    //递归非重子节点
    std::vector<heap_t*> heaps;
    for (int_t to : graph[vtx]) {
        if (to != maxChd[vtx]) {
            auto next = new heap_t;
            DFS2(to, next);
            heaps.push_back(next);
        }
    }
    std::vector<int_t> result;
    //合并答案
    while (true) {
        bool hasNonEmpty = false;
        int_t max = 0;
        for (auto ptr : heaps) {
            if (ptr->empty() == false) {
                max = std::max(max, *(ptr->begin()));
                ptr->erase(ptr->begin());
                hasNonEmpty = true;
            }
        }
        if (hasNonEmpty == false) break;
        assert(heap->empty() == false);
        if (heap->empty() == false) {
            auto ptr = heap->begin();
            max = std::max(max, *ptr);
            heap->erase(ptr);
        }
        result.push_back(max);
    }
    for (auto ptr : heaps) {
        delete ptr;
    }
    result.push_back(vals[vtx]);
    for (int_t x : result) heap->insert(x);
}
int main() {
    scanf("%lld", &n);
    for (int_t i = 1; i <= n; i++) scanf("%lld", &vals[i]);
    for (int_t i = 2; i <= n; i++) {
        int_t x;
        scanf("%lld", &x);
        graph[x].push_back(i);
    }
    depth[1] = 1;
    DFS1(1);
    auto heap = new heap_t;
    DFS2(1, heap);
    int_t result = std::accumulate(heap->begin(), heap->end(), 0ll);
    cout << result << endl;
    return 0;
}