题目背景

P2898

题目描述

但是各位股东们觉得挂灯笼这个方案着实不妥(可能绿色的灯笼确实不太好看)

他们的方案是把所有的摊位安排成树的结构，入口处自然是根节点（0号节点），$n$个摊位分布在节点$1$ ~ $n$上。对于第$i$个摊位，给出可以走到第$i$个摊位的节点$F_i$（不可以从节点$i$走到节点$F_i$）和营业目标$E_i$。同时，由于市场内的神秘魔法能量，节点$F_i$与节点$i$之间连接的路只能允许最多$W_i$个人一次通过。已知每个人都只会在最终到达的摊位购买价格为$1$的物品，且购买后会被立即传送回入口处。若入口处有无穷多个人，那么最多会有多少摊位满足营业目标。

输入格式

第一行一个整数$n$，表示摊位的数量。

接下来$n$行，第$i+1$行有三个整数$F_i$、$E_i$、$W_i$，分别表示$i$号节点的父节点、$i$号摊位的营业目标、连接节点$i$与$F_i$的路最多能允许多少人一次通过。

输出格式

最多会有多少摊位满足营业目标

样例

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

2

数据范围

• 对于$20\%$的数据，满足$1 \le n \le 10, 0 \le F_i \le n, 0 \le E_i, W_i \le 100$。
• 另有$10\%$的数据，满足$1 \le n \le 1000,F_i = 0, 0 \le E_i, W_i \le 100$
• 另有$30\%$的数据，满足$1 \le n \le 1000,F_i = i-1, 0 \le E_i, W_i \le 100$
• 对于$100\%$的数据，满足$1 \le n \le 1000,0 \le F_i \le n, 0 \le E_i, W_i \le 100$