F - Fighter Takahashi Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

N 頂点の木があります。 1 番目の頂点が根であり、i 番目 (2\leq i\leq N) の頂点の親は p _ i\ (1\leq p _ i\lt i) です。

根でない頂点には、敵か薬のどちらか一方が配置されています。 高橋くんは、すべての敵を倒したいです。 はじめ、高橋くんの強さは 1 で、頂点 1 にいます。 i=2,\ldots,N について、i 番目の頂点の情報は整数の組 (t _ i,s _ i,g _ i) を用いて次のように表されます。

  • t _ i=1 ならば i 番目の頂点には敵がいます。この頂点に高橋くんが初めて訪れたとき、高橋くんの強さが s _ i 未満だった場合高橋くんは敵に倒されて敗北し、高橋くんは他の頂点に移動できなくなります。そうでなかった場合、高橋くんは敵を倒し、強さが g _ i 上昇します。
  • t _ i=2 ならば i 番目の頂点には薬があります。この頂点に高橋くんが初めて訪れたとき、高橋くんは薬を飲み、強さが g _ i 倍になります。（薬がある頂点では、s _ i=0 です。）

薬がある頂点はたかだか 10 個です。

高橋くんは、隣接する頂点に移動することができます。 高橋くんがすべての敵を倒すことができるか判定してください。

制約

  • 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)
  • t _ i=2 である頂点は 10 個以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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）を 1 行で出力せよ。

入力例 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 から 2,3,2,1,6,7,6,1,4,5,8 の順に移動することで、すべての敵を倒すことができます。 このとき、高橋くんがいる頂点と高橋くんの強さは以下の図のように変化します（図では、すでに訪れたことのある頂点への移動は省略しています）。

例えば、頂点 1 から 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

Score : 550 points

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