记录编号	321095	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	2300.[APIO 2016] 烟花表演	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.184 s
提交时间	2016-10-13 13:19:34	内存使用	8.11 MiB

#include<cstdio>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int N=300010;
typedef long long ll;
__gnu_pbds::priority_queue<ll> Q[N];
int n,m,fa[N],s[N],up[N],k[N];ll ans;
int main()
{
	freopen("fireworks.in","r",stdin);
	freopen("fireworks.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=2;i<=n+m;i++)
		scanf("%d%d",&fa[i],&up[i]),ans+=up[i];
	for (int i=n+m;i;i--)
		s[i]++,s[fa[i]]+=s[i];
	for (int i=n+1;i<=n+m;i++)
		Q[fa[i]].push(up[i]),Q[fa[i]].push(up[i]),k[fa[i]]++;
	for (int i=n;i>1;i--){
		while ((int)Q[i].size()>k[i]+1) Q[i].pop();
		ll b=Q[i].top();Q[i].pop();
		ll a=Q[i].top();Q[i].pop();
		Q[i].push(a+up[i]);
		Q[i].push(b+up[i]);
		Q[fa[i]].join(Q[i]);
		k[fa[i]]+=k[i];
	}
	while ((int)Q[1].size()>k[1]) Q[1].pop();
	while (!Q[1].empty()) ans-=Q[1].top(),Q[1].pop();
	printf("%lld\n",ans);
	return 0;
}