luogu5290 春节十二响

题目链接

思路

先考虑一条链的情况怎么做。

因为只有两个子树，并且两个子树都是链。所以可以把这两条链找出来，然后\(sort\)一下。合并起来。

然后推广到树上

对于每一棵树都可以按照和上面同样的方法合并成一条链。

这样就可以\(O(n^2logn)\)做了。

考场上就想到这些。而且链的情况还忘了存档。。。

启发式合并

只要对于每个节点维护出一个堆，并且进行启发式合并。就可以达到\(O(nlogn)\)的复杂度了。

还是太菜了。。。

代码

/*

* @Author: wxyww

* @Date:   2019-04-11 20:14:14

* @Last Modified time: 2019-04-11 20:23:59

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<ctime>

using namespace std;

typedef long long ll;

const int N = 200000 + 100;

ll read() {

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') {

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

		c=getchar();

	}

	while(c>='0'&&c<='9') {

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

		c=getchar();

	}

	return x*f;

}

priority_queue<int>q[N];

vector<int>e[N];

int a[N],dy[N];

int tmp[N];

int merge(int x,int y) {

	if(q[x].size() < q[y].size()) swap(x,y);

	int js = 0;

	while(!q[y].empty()) {

		tmp[++js] = max(q[y].top(),q[x].top());

		q[y].pop();q[x].pop();

	}

	for(int i = 1;i <= js;++i) q[x].push(tmp[i]);

	return x;

}

void dfs(int u) {

	int k = e[u].size();

	dy[u] = u;

	for(int i = 0;i < k;++i) {

		int v = e[u][i];

		dfs(v);

		dy[u] = merge(dy[u],dy[v]);

	}

	q[dy[u]].push(a[u]);

}

int main() {

	int n = read();

	for(int i = 1;i <= n;++i) a[i] = read();

	for(int i = 2;i <= n;++i) e[read()].push_back(i);

	dfs(1);

	ll ans = 0;

	while(!q[dy[1]].empty()) {

		ans += q[dy[1]].top();q[dy[1]].pop();

	}

	cout<<ans;

	return 0;

}