分数: 550 点
问题陈述
有一棵树 N 顶点。 的 1-st 顶点是根,是 i- 第一个顶点 (2\leq i\leq N) is p _ i\ (1\leq p _ i\lt i).
每个非根顶点都有一个 敌人 或 医药 就可以了。 高桥想要打败所有的敌人。 最初他的实力是 1,他在顶点 1。 对于 i=2,\ldots,N的信息 i-th 顶点由整数三元组表示 (t _ i,s _ i,g _ i) 如下。
- If t _ i=1,有一个敌人 i- 第一个顶点。当高桥第一次访问这个顶点时,如果他的力量小于 s _ i,高桥被敌人击败, 输了,之后他无法移动到其他顶点。否则,他击败敌人,他的力量增加 g _ i.
- If t _ i=2,那里有一种药 i- 第一个顶点。当高桥第一次造访这个顶点时,他服用了药物,他的力量乘以 g _ i。 (对于带有药物的顶点, s _ i=0.)
最多有 10 顶点用药。
Takahashi 可以重复移动到相邻顶点。 确定他是否可以击败所有敌人。
约束
- 2\leq N\leq 500
- 1\leq p _ i\lt i\ (2\leq i\leq N)
- t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
- t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
- t _ i=2\implies s _ i=0\ (2\leq i\leq N)
- 1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
- 最多有 10 顶点 t _ i=2.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N p _ 2 t _ 2 s _ 2 g _ 2 p _ 3 t _ 3 s _ 3 g _ 3 \vdots p _ N t _ N s _ N g _ N
输出
打印答案 (Yes or No)在一行中。
示例输入 1
8 1 2 0 3 2 1 3 3 1 2 0 4 4 1 2 2 1 2 0 5 6 1 5 5 5 1 140 1
示例输出 1
Yes
最初,树看起来像这样:

高桥可以通过从顶点移动来击败所有敌人 1 to 2,3,2,1,6,7,6,1,4,5,8 按此顺序。 这里,他的位置和强度变化如下图所示(已访问过的顶点的移动被省略)。

另一方面,如果他从顶点移动 1 to 4,5,8 按照这个顺序,例如,他访问顶点时的强度 8 将小于 s _ 8=140,所以他没有打败所有敌人就输了。
示例输入 2
12 1 1 166 619 1 1 17 592 2 1 222 983 2 1 729 338 5 1 747 62 3 1 452 815 3 2 0 1 4 2 0 40 4 1 306 520 6 1 317 591 1 1 507 946
示例输出 2
No
示例输入 3
12 1 1 1 791 2 2 0 410 2 1 724 790 2 1 828 599 5 2 0 13 3 1 550 803 1 1 802 506 5 1 261 587 6 1 663 329 8 1 11 955 9 1 148 917
示例输出 3
Yes
示例输入 4
12 1 2 0 1000000000 2 2 0 1000000000 3 2 0 1000000000 4 2 0 1000000000 5 2 0 1000000000 6 2 0 1000000000 7 2 0 1000000000 8 2 0 1000000000 9 2 0 1000000000 10 2 0 1000000000 11 1 1 1
示例输出 4
Yes