3425.能量获取

Time Limits: 1000 ms Memory Limits: 131072 KB

Description

“封印大典启动,请出Nescafe魂珠!”随着圣主applepi一声令下,圣剑护法rainbow和魔杖护法freda将Nescafe魂珠放置于封印台上。封印台是一个树形的结构,魂珠放置的位置就是根节点(编号为0)。还有n个其他节点(编号1-n)上放置着封印石,编号为i的封印石需要从魂珠上获取Ei的能量。能量只能沿着树边从魂珠传向封印石,每条边有一个能够传递的能量上限Wi,魂珠的能量是无穷大的。作为封印开始前的准备工作,请你求出最多能满足多少颗封印台的能量需求?

注意:能量可以经过一个节点,不满足它的需求而传向下一个节点。每条边仅能传递一次能量。

Input

第一行一个整数n,表示除根节点之外的其他节点的数量。

接下来n行,第i+1行有三个整数Fi、Ei、Wi,分别表示i号节点的父节点、i号节点上封印石的能量需求、连接节点i与Fi的边最多能传递多少能量。

Output

最多能满足多少颗封印石的能量需求。

Sample Input

1
2
3
4
5
4 
0 3 2
0 100 100
1 1 1
2 75 80

Sample Output

1
2

Data Constraint

对于100%的数据,满足1<=n<=1000,0<=Fi<=n,0<=Ei,Wi<=100

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
int n,ans,f[1010],w[1010];
struct tree{
int e,b;
}k[1010];
bool cmp(tree a,tree b){
return a.e<b.e;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d%d",&f[i],&k[i].e,&w[i]);
k[i].b=i;
}
sort(k+1,k+n+1,cmp);
int j;
for (int i=1;i<=n;i++)
{
for (j=k[i].b;j;j=f[j]){
if (w[j]<k[i].e){
break;
}
}
if (j){
continue;
}
for (j=k[i].b;j;j=f[j]){
w[j]-=k[i].e;
}
ans++;
}
printf("%d",ans);
return 0;
}