战士高桥

题目描述

有一棵 $N$ 个顶点的树。 第 $1$ 个顶点为根,第 $i$ 个顶点 $(2 \le i \le N)$ 的父节点为 $p_i$ $(1 \le p_i \lt i)$。

每个非根顶点上有一个敌人或一份药品。 Takahashi 想要击败所有敌人。 最初,他的战斗力为 $1$,位于顶点 $1$。 对于 $i = 2, \ldots, N$,第 $i$ 个顶点的信息由三个整数 $(t_i, s_i, g_i)$ 表示,含义如下:

• 若 $t_i = 1$,则第 $i$ 个顶点上有敌人。当 Takahashi 第一次访问该顶点时,如果他的战斗力小于 $s_i$,他会被敌人击败而失败,之后无法移动到其他顶点。否则,他击败敌人,战斗力增加 $g_i$。
• 若 $t_i = 2$,则第 $i$ 个顶点上有药品。当 Takahashi 第一次访问该顶点时,他服下药品,战斗力变为原来的 $g_i$ 倍。(对于有药品的顶点,$s_i = 0$。)

有药品的顶点至多有 $10$ 个。

Takahashi 可以反复移动到相邻的顶点。 判断他能否击败所有敌人。

输入格式

输入按以下格式从标准输入给出。

$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 或 No)。

样例

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

Yes

Takahashi 可以按顶点 $1 \to 2 \to 3 \to 2 \to 1 \to 6 \to 7 \to 6 \to 1 \to 4 \to 5 \to 8$ 的顺序移动,从而击败所有敌人。

另一方面,例如若他按顶点 $1 \to 4 \to 5 \to 8$ 的顺序移动,访问顶点 $8$ 时他的战斗力将小于 $s_8 = 140$,因此他会在击败所有敌人之前失败。

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

No

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

Yes

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

Yes

数据范围

• $2 \le N \le 500$
• $1 \le p_i \lt i\ (2 \le i \le N)$
• $t_i \in \lbrace1, 2\rbrace\ (2 \le i \le N)$
• $t_i = 1 \implies 1 \le s_i \le 10^9\ (2 \le i \le N)$
• $t_i = 2 \implies s_i = 0\ (2 \le i \le N)$
• $1 \le g_i \le 10^9\ (2 \le i \le N)$
• 满足 $t_i = 2$ 的顶点至多有 $10$ 个。
• 所有输入值均为整数。