记录编号	56503	评测结果	AAAAAAAAAA
题目名称	立春树	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.161 s
提交时间	2013-03-31 10:00:43	内存使用	11.67 MiB

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("tdec.in");
ofstream fout("tdec.out");
typedef long long ll;
const long long Inf=123456789;
const ll Nx=200000;
class Node
{
public:
	ll Name;
	Node *Prev;
}*last[Nx];
ll Vn,C[Nx],T[Nx],f[Nx],t[Nx],m[Nx];//f是总耗时，t是总数量
void Add(ll u,ll v)
{
Node *temp=new Node;
	temp->Name=v;
	temp->Prev=last[u];
	last[u]=temp;
}
void Initialize()
{
ll p;
	fin>>Vn;
	for(ll i=1;i<=Vn;i++)
	{
		fin>>p>>C[i]>>T[i];
		if(p>0)
			Add(p,i);
	}
}
void dfs(ll pos)
{
Node *p;
	m[pos]=Inf;
	for(p=last[pos];p;p=p->Prev)
	{
		dfs(p->Name);
		t[pos]+=t[p->Name];
		f[pos]+=f[p->Name];
		m[pos]=min(m[pos],m[p->Name]);
	}
	m[pos]=min(m[pos],T[pos]);
	if(t[pos]<C[pos])
		f[pos]+=(C[pos]-t[pos])*m[pos];
	t[pos]=max(C[pos],t[pos]);
}
int main()
{
	Initialize();
	
	dfs(1);
	
	fout<<f[1]<<endl;
	
	fin.close();
	fout.close();
	return 0;
}