记录编号	23692	评测结果	AAAAAAAAAA
题目名称	立春树	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.328 s
提交时间	2011-03-17 14:52:51	内存使用	4.45 MiB

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

using namespace std;
struct edge
{
	int t;
	edge *next;
}E[200001],*V[100001];
int eh,n;
long long C[100001],T[100001];
long long cost[100001];
inline void addedge(int a,int b)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t=b;
}

void init()
{
	scanf("%d",&n);
	int t;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%lld%lld",&t,C+i,T+i);
		if (i!=1) addedge(t,i);
	}
	
}

void dp(int u)
{
	long long sum=0;
	for (edge *e=V[u];e;e=e->next)
	{
		dp(e->t);
		sum+=C[e->t];
		cost[u]+=cost[e->t];
		if (T[e->t]<T[u]) T[u]=T[e->t];
	}
	if (sum<C[u]) cost[u]+=T[u]*(C[u]-sum);
	else C[u]=sum;
}

int main()
{
	freopen("tdec.in","r",stdin);
	freopen("tdec.out","w",stdout);
	init();
	dp(1);
	printf("%lld\n",cost[1]);
	return 0;
}