记录编号	259914	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2016] 烟花表演	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	10.184 s
提交时间	2016-05-11 22:44:03	内存使用	33.50 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
//#include<cassert>
#include<vector>
using namespace std;
typedef long long LL;
const int SIZEN=300010;
int n,m,N;
vector<pair<LL,LL> > c[SIZEN];
bool isleaf(int x){
	return x!=1&&c[x].size()==1;	
}
class Node{//big root
public:
	int l,r;
	LL h;
	LL val;
	Node(){l=r=h=val=0;}
	Node(LL _v){
		h=1;
		val=_v;
	}
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define h(x) tree[x].h
	#define val(x) tree[x].val
};
Node tree[4*SIZEN];
int root[SIZEN]={0};
int tot=0;
void dfsprint(int x){
	if(!x) return;
	cout<<"node: "<<x<<" "<<val(x)<<" "<<l(x)<<" "<<r(x)<<endl;
	dfsprint(l(x));
	dfsprint(r(x));
}
void give_list(int x,vector<LL> &v){
	if(!x) return;
	v.push_back(val(x));
	give_list(l(x),v);
	give_list(r(x),v);
}
void print_list(int x){
	vector<LL> v;
	give_list(root[x],v);
	cout<<x<<endl;for(int i=0;i<v.size();i++) cout<<v[i]<<" ";cout<<endl;
}
int merge(int u,int v){
	if(!u||!v) return u+v;
	if(val(u)<val(v)) swap(u,v);
	r(u)=merge(r(u),v);
	if(h(l(u))<h(r(u))) swap(l(u),r(u));
	h(u)=h(r(u))+1;
	return u;
}
int pop(int x){
	return merge(l(x),r(x));
}
int add_faedge(int x,int d,LL w){//x号堆节点,它有d个儿子,它的父亲边长度为w 
	while(d>1){
		x=pop(x);
		d--;
	}
	LL l,r;
	r=val(x);
	x=pop(x);
	l=val(x);
	x=pop(x);
	int p=++tot;
	h(p)=1,val(p)=l+w;
	int q=++tot;
	h(q)=1,val(q)=r+w;
	x=merge(x,p);
	x=merge(x,q);
	return x;
}
int fa[SIZEN]={0};
int make_hull(int x){
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i].first;LL w=c[x][i].second;
		if(u>n){
			int p=++tot;
			h(p)=1,val(p)=w;
			int q=++tot;
			h(q)=1,val(q)=w;
			root[u]=merge(p,q);
			root[x]=merge(root[x],root[u]);
		}
		else{
			root[u]=add_faedge(root[u],c[u].size(),w);
			root[x]=merge(root[x],root[u]);
		}
	}
}
void work(void){
	for(int i=n;i>=1;i--) make_hull(i);
}
LL valsum=0;
vector<LL> points;
void answer(void){
	int x=root[1];
	while(x){
		points.push_back(val(x));
		x=pop(x);
	}
	sort(points.begin(),points.end());
	LL k=(LL)c[1].size()-points.size(),b=valsum;
	for(int i=0;i<points.size();i++){
		LL x=points[i];
		k++,b-=x;
		if(k==0){
			LL ans=x*k+b;
			cout<<ans<<endl;
			break;
		}
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	N=n+m;
	for(int i=2;i<=N;i++){
		int p,w;
		scanf("%d%d",&p,&w);
		c[p].push_back(make_pair(i,w));
		//c[i].push_back(make_pair(p,w));
		valsum+=w;
	}
}
int main(void){
	freopen("fireworks.in","r",stdin);
	freopen("fireworks.out","w",stdout); 
	read();
	work();
	answer();
	return 0;
}