还有33天就要高考了，我在干啥……

题目概述

一棵有根树，每个节点有权值。

要求把所有节点分成组，具有祖先-后代关系的两个节点不能被分到同一组。

每一组的代价是所包含的节点的最大权值，最小化所有组的代价之和。

题解

想了半天的树剖也没想出来，放弃梦想去看题解……（你怎么不先想想部分分啊喂）

发现是启发式合并。

考虑一条链（1号节点在中间的某个位置）咋做。

这棵树的形状是1号节点下面挂着两条长链。隶属于同一条链的节点都不能放在一组。那么只需要把两条链各自的最大值节点放到一组，各自的次大值节点放到一组……一条链被用完了，另一条中剩下的节点分别自成一组。

那么假如1号节点下面有更多条链呢？只需要合并完两条之后再把第三条合并进去，方法和上面相同。

那么整棵树其实也dfs然后对每个节点这么合并所有的儿子就好了。这个找最大值再找次大值再找次次大值……的数据结构，显然用堆。

如何优化复杂度呢？启发式合并。把每个节点的儿子按照对应堆的大小排个序，然后把小的往大的合并。这个启发式合并吧，和我们熟知的那个启发式合并还不太一样，复杂度非常神奇，合并两个堆之后新堆的大小是原先较大堆的大小，而合并需要的push、pop操作数是原先较小堆的大小。相当于把较小堆的每个元素以\(O(\log n)\)的复杂度“删去”了，“删去”以后就不再对总复杂度造成代价了。总共最多“删去”n个节点，每次复杂度\(O(\log n)\)，总复杂度\(O(n\log n)\)。

写代码的时候会陷入僵局——若要保证复杂度正确，对应堆最大的那个儿子不能对复杂度做出贡献，也就是你不能动它的堆。然而全合并完之后，那个堆里面的东西要存在父亲节点对应的堆里面。昨天晚上我懵逼半天之后选择去睡觉，今天上数学课走神的时候才想到咋整……给每个节点设置个“id”，表示对应的堆的编号，这样堆存的地方不用动，交换父亲和最大儿子的id即可。

代码

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <queue>

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef long long ll;

template <class T>

void read(T &x){

    bool op = 0;

    char c;

    while(c = getchar(), c < '0' || c > '9')

        if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

        x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 200005;

int n, id[N];

ll w[N], ans;

vector <int> son[N];

priority_queue <int> que[N];

bool cmp(int a, int b){

    return que[id[a]].size() > que[id[b]].size();

}

void dfs(int u){

    vector <int> buf;

    for(auto v: son[u])

        dfs(v);

    sort(son[u].begin(), son[u].end(), cmp);

    for(auto v: son[u]){

        if(que[id[u]].empty()) swap(id[u], id[v]);

        else{

            while(!que[id[v]].empty()){

                int u_top = que[id[u]].top(), v_top = que[id[v]].top();

                que[id[u]].pop(), que[id[v]].pop();

                buf.push_back(max(u_top, v_top));

            }

            for(auto x: buf)

                que[id[u]].push(x);

            buf.clear();

        }

    }

    que[id[u]].push(w[u]);

}

int main(){

    read(n);

    for(int i = 1; i <= n; i++)

        read(w[i]), id[i] = i;

    for(int i = 2, f; i <= n; i++)

        read(f), son[f].push_back(i);

    dfs(1);

    while(!que[id[1]].empty())

        ans += que[id[1]].top(), que[id[1]].pop();

    write(ans), enter;

    return 0;

}