记录编号	259805	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2016] 烟花表演	最终得分	100
用户昵称	APIO棒子出题人	是否通过	通过
代码语言	C++	运行时间	9.428 s
提交时间	2016-05-11 17:36:47	内存使用	78.28 MiB

/*
 * Author: Gyeonggeun Kim(kriii)
 * Time Complexity: O(N lg N)
 */
#include <stdio.h>

const int Z = 1<<21;

int N,M,V,par[Z/2],dist[Z/2],child[Z/2],size[Z/2],st[Z/2],ed[Z/2];
long long my[Z/2];

struct node{
	node(){
		x = i = 0;
	}
	node(long long x_, int i_){
		x = x_; i = i_;
	}
	long long x; int i;

	bool operator <(const node &t)const{
		return x < t.x;
	};

	node operator +(const node &t)const{
		if (x < t.x) return t;
		return (*this);
	}
}I[Z*2];

void in(long long x, int i)
{
	I[i+Z] = node(x,i);
	i = (i + Z) >> 1;
	while (i){
		I[i] = I[i*2] + I[i*2+1];
		i >>= 1;
	}
}

node out(int i, int j)
{
	node res;
	i += Z; j += Z;
	while (i < j){
		if (i & 1){
			if (res < I[i]) res = I[i];
			i++;
		}
		if (~j & 1){
			if (res < I[j]) res = I[j];
			j--;
		}
		i >>= 1; j >>= 1;
	}
	if (i == j){
		if (res < I[i]) res = I[i];
	}
	return res;
}

long long remove(int s, int e)
{
	node t = out(s,e);
	in(0,t.i);
	return t.x;
}

int main()
{
	freopen("fireworks.in","r",stdin);
	freopen("fireworks.out","w",stdout);
	scanf ("%d %d",&N,&M); V = N + M;

	for (int i=2;i<=V;i++){
		scanf ("%d %d",&par[i],&dist[i]);
		child[par[i]]++;
	}

	for (int i=V;i>=1;i--){
		size[i]++;
		size[par[i]] += size[i];
	}

	ed[1] = 1;
	for (int i=2;i<=V;i++){
		st[i] = ed[par[i]] + 1;
		ed[i] = st[i] + 1;
		ed[par[i]] = st[i] + size[i] * 2 - 1;
	}

	for (int i=V;i>=2;i--){
		int s = st[i], e = ed[i];
		for (int k=1;k<child[i];k++) my[i] += remove(s,e);
		long long p = remove(s,e);
		long long q = remove(s,e);
		in(dist[i]+p,s);
		in(dist[i]+q,s+1);
		my[i] -= dist[i];
		my[par[i]] += my[i];
	}

	for (int k=0;k<child[1];k++) my[1] += remove(st[1],ed[1]);
	printf ("%lld\n",my[1]);

	return 0;
}