Score : $550$ points

问题描述

存在一棵包含 $N$ 个顶点的树。第1个顶点为根节点，第 $i$（$2\leq i\leq N$）个顶点的父节点为$p _ i$（$1\leq p _ i<i$）。

每个非根顶点上有一个敌人或一种药剂。高桥想要击败所有敌人。初始时，他的力量值为 $1$，并且位于顶点 $1$。对于第 $i$（$i=2,\ldots,N$）个顶点的信息由一个包含三个整数的元组 $(t _ i,s _ i,g _ i)$ 表示，如下所示：

• 若 $t _ i=1$，则在第 $i$ 个顶点上有一个敌人。当高桥首次访问这个顶点时，如果他的力量值小于 $s _ i$，他会被敌人击败并失败，之后无法移动到其他顶点。否则，他将击败敌人，并且他的力量值增加 $g _ i$。
• 若 $t _ i=2$，则在第 $i$ 个顶点上有一种药剂。当高桥首次访问这个顶点时，他会获取药剂，其力量值会乘以 $g _ i$。（对于拥有药剂的顶点，$s _ i=0$。）

最多有 $10$ 个顶点含有药剂。

高桥可以重复地移动到相邻顶点。判断他是否能够击败所有敌人。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a tree with $N$ vertices. The $1$-st vertex is the root, and the parent of the $i$-th vertex $(2\leq i\leq N)$ is $p _ i\ (1\leq p _ i\lt i)$.

Each non-root vertex has an enemy or a medicine on it. Takahashi wants to defeat all the enemies. Initially, his strength is $1$, and he is at vertex $1$. For $i=2,\ldots,N$, the information of the $i$-th vertex is represented by a triple of integers $(t _ i,s _ i,g _ i)$ as follows.

• If $t _ i=1$, there is an enemy at the $i$-th vertex. When Takahashi visits this vertex for the first time, if his strength is less than $s _ i$, Takahashi is defeated by the enemy and loses, after which he cannot move to other vertices. Otherwise, he defeats the enemy, and his strength increases by $g _ i$.
• If $t _ i=2$, there is a medicine at the $i$-th vertex. When Takahashi visits this vertex for the first time, he takes the medicine, and his strength is multiplied by $g _ i$. (For a vertex with a medicine, $s _ i=0$.)

There are at most $10$ vertices with a medicine.

Takahashi can repeatedly move to an adjacent vertex. Determine if he can defeat all the enemies.

Constraints

• $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)$
• There are at most $10$ vertices with $t _ i=2$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print the answer (Yes or No) in one line.

Sample Input 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

Sample Output 1

Yes

Initially, the tree looks like this:

Takahashi can defeat all the enemies by moving from vertex $1$ to $2,3,2,1,6,7,6,1,4,5,8$ in this order. Here, his position and strength change as shown in the following figure (movements to vertices that have already been visited are omitted).

On the other hand, if he moves from vertex $1$ to $4,5,8$ in this order, for example, his strength when visiting vertex $8$ will be less than $s _ 8=140$, so he will lose without defeating all the enemies.

Sample Input 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

Sample Output 2

No

Sample Input 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

Sample Output 3

Yes

Sample Input 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

Sample Output 4

Yes

update @ 2024/3/10 09:08:06