TYVJ P2064(点的向上维护）

P2064 - 「Poetize10」能量获取From lydliyudong Normal (OI)
总时限：10s 内存限制：128MB 代码长度限制：64KB

描述 Description“封印大典启动，请出Nescafe魂珠！”随着圣主applepi一声令下，圣剑护法rainbow和魔杖护法freda将Nescafe魂珠放置于封印台上。封印台是一个树形的结构，魂珠放置的位置就是根节点（编号为0）。还有n个其它节点（编号1~n）上放置着封印石，编号为i的封印石需要从魂珠上获取Ei的能量。能量只能沿着树边从魂珠传向封印石，每条边有一个能够传递的能量上限Wi，魂珠的能量是无穷大的。作为封印开始前的准备工作，请你求出最多能满足多少颗封印石的能量需求？
注意：能量可以经过一个节点，不满足它的需求而传向下一个节点。每条边仅能传递一次能量。

输入格式 InputFormat第一行一个整数n，表示除根节点之外其它节点的数量。
接下来n行，第i+1行有三个整数Fi、Ei、Wi，分别表示i号节点的父节点、i号节点上封印石的能量需求、连接节点i与Fi的边最多能传递多少能量。

样例输入 SampleInput [复制数据]

40 3 20 100 1001 1 12 75 80

样例输出 SampleOutput [复制数据]

2

数据范围和注释 Hint对于 100% 的数据，满足1<=n<=1000，0<=Fi<=n，0<=Ei,Wi<=100。

时间限制 TimeLimitation各个测试点1s

此题贪心 贪最小的点，易证必最优解

Program energy;const   maxn=1000;var   n,i,j,ans:longint;   f,e,w,num,hpos:array[0..maxn] of longint;procedure swap(var a,b:longint);var   t:longint;begin   t:=a;a:=b;b:=t;end;function max(a,b:longint):longint;begin   if a>b then exit(a) else exit(b);end;function min(a,b:longint):longint;begin   if a<b then exit(a) else exit(b);end;procedure qsort(l,r:longint);var   i,j,m,p:longint;begin   i:=l;   j:=r;   m:=e[(l+r) div 2];   repeat      while (e[i]<m) do inc(i);      while (e[j]>m) do dec(j);      if (i<=j) then      begin         swap(e[i],e[j]);         swap(f[i],f[j]);         swap(w[i],w[j]);         swap(num[i],num[j]);         inc(i);dec(j);      end;   until i>j;   if (l<j) then qsort(l,j);   if (i<r) then qsort(i,r);end;procedure pour(x:longint);var   noww,i,j:longint;begin   noww:=maxlongint;   i:=x;   while (i<>0) do   begin      noww:=min(noww,w[i]);      i:=hpos[f[i]];   end;   if (noww<e[x]) then exit;   inc(ans);   i:=x;   while (i<>0) do   begin      dec(w[i],e[x]);      i:=hpos[f[i]];   end;end;begin   readln(n);   for i:=1 to n do   begin      read(f[i],e[i],w[i]);      num[i]:=i;   end;   qsort(1,n);   hpos[0]:=0;   for i:=1 to n do hpos[num[i]]:=i;//   for i:=1 to n do write(f[i],' ',e[i],' ',w[i]);   ans:=0;   for i:=1 to n do pour(i);   writeln(ans);end.