记录编号	404044	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2016] 烟花表演	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.812 s
提交时间	2017-05-12 16:21:20	内存使用	7.18 MiB

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