[十二省联考2019]春节十二响（启发式合并)

• 链的情况我们的做法是从两个子树中各取出最大的， 贡献答案是两个的较大值， 直到其中一个没有数字了， 我们就停止， 然后加入还有数字的那棵子树中所有的数字贡献

• 显然这是一个类似堆的操作， 同时我们可以将它扩充到许多棵子树的情况， 实际上就是取出每颗子树堆的最大值合并起来

• 这样的话就能够打出一个用堆模拟的暴力（能A）

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long
#define mmp make_pair
#define M 200010
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
int sz[M], fa[M], son[M], a[M], n, tmp[M], tp, id[M], tim;
vector<int> to[M];
bool cmp(int a, int b)
{
    return sz[a] > sz[b];
}
ll ans = 0;
priority_queue<int> q[M];

void dfs(int now)
{
	id[now] = ++tim;
    for(int i = 0; i < to[now].size(); i++)
    {
        int vj = to[now][i];
        dfs(vj);
    }
    sort(to[now].begin(), to[now].end(), cmp);
    int r = to[now].size() - 1, tp = 0;
    while(1)
    {
    	int maxx = 0;
    	for(int i = 0; i <= r; i++)
    	{
    		int vj = to[now][i];
    		if(q[id[vj]].empty())
    		{
    			r = i - 1;
    			break;
    		}
    		maxx = max(maxx, q[id[vj]].top());
    		q[id[vj]].pop();
    		sz[vj]--;
    	}
    	if(maxx != 0) tmp[++tp] = maxx;
    	if(r <= 0) break;
    }
	if(to[now].size()) id[now] = id[to[now][0]], sz[now] = sz[to[now][0]];
	for(int i = 1; i <= tp; i++) q[id[now]].push(tmp[i]);
	q[id[now]].push(a[now]);
	sz[now] += tp + 1;
}

int main() {
//	freopen("spring.in", "r", stdin);freopen("spring.out", "w", stdout);
    n = read();
    for(int i = 1; i <= n; i++) a[i]  = read();
    for(int i = 2; i <= n; i++) {
        fa[i] = read();
        to[fa[i]].push_back(i);
    }
    dfs(1);
    while(!q[id[1]].empty()) ans += q[id[1]].top(), q[id[1]].pop();
    cout << ans << "
";
    return 0;
}
/*
16
8 9 19 9 13 9 17 8 9 20 20 7 2 12 19 6
1 2 1 4 3 5 5 8 6 10 3 8 7 4 3


*/

• 排序之后直接用堆合并就能A, 但是这样我不太清楚复杂度是多少
• 考虑直接合并所有子树和依次合并两个子树效果是一样的
• 然后我们就可以在合并的时候把小的往大的里面合
• 然后启发式的复杂度就是两个log的了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long
#define mmp make_pair
#define M 200010
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
int sz[M], fa[M], son[M], a[M], n, id[M], tim;
vector<int> to[M];
ll ans = 0;
priority_queue<int> q[M];

void dfs(int now)
{
    id[now] = ++tim;
    for(int i = 0; i < to[now].size(); i++)
    {
        int vj = to[now][i];
        dfs(vj);
    }
    for(int i = 0; i < to[now].size(); i++)
    {
        int vj = to[now][i];
        if(q[id[now]].size() < q[id[vj]].size()) swap(id[now], id[vj]);
        int m = q[id[vj]].size();
        for(int j = 1; j <= m; j++)
        {
            son[j] = max(q[id[now]].top(), q[id[vj]].top());
            q[id[now]].pop(), q[id[vj]].pop();
        }
        for(int j = 1; j <= m; j++) q[id[now]].push(son[j]);
    }
    q[id[now]].push(a[now]);
    
}

int main() {
//	freopen("spring.in", "r", stdin);freopen("spring.out", "w", stdout);
    n = read();
    for(int i = 1; i <= n; i++) a[i]  = read();
    for(int i = 2; i <= n; i++) {
        fa[i] = read();
        to[fa[i]].push_back(i);
    }
    dfs(1);
    while(!q[id[1]].empty()) ans += q[id[1]].top(), q[id[1]].pop();
    cout << ans << "
";
    return 0;
}