记录编号	23678	评测结果	AAAAAAAAAA
题目名称	立春树	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	0.370 s
提交时间	2011-03-17 12:04:22	内存使用	4.50 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=111111;

long long n,m,i,j,k,c[MAXN],h,t,s,sum[MAXN],need[MAXN],ans;
int f[MAXN],inn[MAXN],Q[MAXN*2];

int main()
{
	freopen("tdec.in","r",stdin);
	freopen("tdec.out","w",stdout);
	scanf("%d",&n);
	memset(inn,0,sizeof(inn));
	for (i=1;i<=n;i++)
	{
		//cin>>f[i]>>need[i]>>c[i];
		scanf("%d%d%d",&f[i],&need[i],&c[i]);
		if (f[i]!=-1) ++inn[f[i]];
	}
	t=0;
	h=1;
	for (i=1;i<=n;i++)
		if (inn[i]==0)
		{
			Q[++t]=i;
			++s;
		}
	for (;;)
	{
		k=Q[h];
		if (sum[k]<need[k])
		{
			ans+=(need[k]-sum[k])*c[k];
			sum[k]=need[k];
		}
		if (k==1) break;
		sum[f[k]]+=sum[k];
		if (c[k]<c[f[k]]) c[f[k]]=c[k];
		--inn[f[k]];
		if (inn[f[k]]==0)
		{
			Q[++t]=f[k];
		}
		++h;
	}
	cout<<ans<<endl;
	return 0;
}