/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は N 個の分岐点からなる灌漑用の水路ネットワークを管理しています。分岐点には 1 から N までの番号が付けられており、分岐点 1 が最上流の水源です。分岐点 i（ 2 \leq i \leq N ）の親は分岐点 P_i であり、全体として分岐点 1 を根とする根付き木をなしています。水は親から子へと流れる構造になっています。
各分岐点 i には、現在 V_i リットルの水が溜まっています。
高橋君は「排水」操作を 0 回以上繰り返し行うことで、全ての分岐点の水量をちょうど 0 にしたいと考えています。操作の回数に上限はなく、また各操作で選ぶ分岐点は自由に決めてよく、同じ分岐点を何度選んでもかまいません。
1 回の「排水」操作は次のように行います。
- 分岐点を 1 つ選ぶ（選んだ分岐点を u とする）。
- u から根（分岐点 1 ）までの木上のパスに含まれる全ての分岐点（ u 自身および分岐点 1 を含む）の水量を、同時に 1 ずつ減少させる。
例えば u = 1 の場合は、分岐点 1 の水量のみが 1 減少します。
ただし、各操作の実行後において、全ての分岐点の水量が 0 以上でなければなりません。 すなわち、操作の結果いずれかの分岐点の水量が負になるような操作は行うことができません。
全ての分岐点の水量をちょうど 0 にすることが可能かどうかを判定してください。可能ならば Yes を、不可能ならば No を出力してください。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq P_i \leq i - 1（ 2 \leq i \leq N ）
- 0 \leq V_i \leq 10^9（ 1 \leq i \leq N ）
- 入力はすべて整数である。
入力
N P_2 P_3 \ldots P_N V_1 V_2 \ldots V_N
- 1 行目には、分岐点の数を表す整数 N が与えられる。
- 2 行目には、分岐点 2 から分岐点 N までの親を表す N-1 個の整数 P_2, P_3, \ldots, P_N がスペース区切りで与えられる。ただし N = 1 の場合、2 行目には何も書かれていない（空行である）。
- 3 行目には、各分岐点の初期水量を表す N 個の整数 V_1, V_2, \ldots, V_N がスペース区切りで与えられる。
出力
全ての分岐点の水量をちょうど 0 にすることが可能ならば Yes を、不可能ならば No を 1 行で出力せよ。
入力例 1
5 1 1 2 2 7 4 2 1 2
出力例 1
Yes
入力例 2
3 1 1 1 1 1
出力例 2
No
入力例 3
12 1 1 2 2 3 3 4 4 6 6 10 20 8 10 3 3 10 0 2 1 5 4 2
出力例 3
Yes
入力例 4
25 1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 9 10 10 12 12 14 16 16 20 35 10 15 6 7 2 9 4 1 5 1 4 2 6 3 4 0 4 1 3 2 5 1 2 3
出力例 4
No
入力例 5
1 1000000000
出力例 5
Yes
Score : 366 pts
Problem Statement
Takahashi manages an irrigation water channel network consisting of N junction points. The junction points are numbered from 1 to N, and junction point 1 is the uppermost water source. The parent of junction point i (2 \leq i \leq N) is junction point P_i, and the entire structure forms a rooted tree with junction point 1 as the root. Water flows from parent to child.
Each junction point i currently holds V_i liters of water.
Takahashi wants to make the water volume at all junction points exactly 0 by performing the "drain" operation zero or more times. There is no upper limit on the number of operations, and the junction point chosen for each operation can be freely decided. The same junction point may be chosen multiple times.
One "drain" operation is performed as follows:
- Choose one junction point (let the chosen junction point be u).
- Simultaneously decrease the water volume by 1 at all junction points on the path from u to the root (junction point 1) in the tree (including u itself and junction point 1).
For example, if u = 1, only the water volume at junction point 1 decreases by 1.
However, after each operation is performed, the water volume at all junction points must be 0 or greater. That is, an operation that would result in the water volume at any junction point becoming negative cannot be performed.
Determine whether it is possible to make the water volume at all junction points exactly 0. If possible, output Yes; if impossible, output No.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
- 0 \leq V_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers.
Input
N P_2 P_3 \ldots P_N V_1 V_2 \ldots V_N
- The first line contains an integer N representing the number of junction points.
- The second line contains N-1 integers P_2, P_3, \ldots, P_N separated by spaces, representing the parents of junction points 2 through N. If N = 1, the second line is empty.
- The third line contains N integers V_1, V_2, \ldots, V_N separated by spaces, representing the initial water volume at each junction point.
Output
Output Yes on a single line if it is possible to make the water volume at all junction points exactly 0, and No otherwise.
Sample Input 1
5 1 1 2 2 7 4 2 1 2
Sample Output 1
Yes
Sample Input 2
3 1 1 1 1 1
Sample Output 2
No
Sample Input 3
12 1 1 2 2 3 3 4 4 6 6 10 20 8 10 3 3 10 0 2 1 5 4 2
Sample Output 3
Yes
Sample Input 4
25 1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 9 10 10 12 12 14 16 16 20 35 10 15 6 7 2 9 4 1 5 1 4 2 6 3 4 0 4 1 3 2 5 1 2 3
Sample Output 4
No
Sample Input 5
1 1000000000
Sample Output 5
Yes