概要

本問題は、根付き木に対して「ある頂点を選び、その頂点から根までのパス上の全頂点の値を \(1\) 減らす」という操作を繰り返すことで、すべての頂点の値をちょうど \(0\) にできるかを判定する問題です。

一見複雑な木上の操作に見えますが、操作の性質を整理することで、各頂点とその「直接の子」との関係性だけに注目した非常にシンプルな条件に帰着できます。

考察

1. 操作による値の減少ルールを整理する

ある頂点 \(u\) を選んで操作を行うと、 \(u\) から根（頂点 \(1\)）までのパス上にあるすべての頂点の値が \(1\) 減少します。 これを逆の視点から捉え直してみましょう。

「ある頂点 \(i\) の値が減少するのは、どのような操作を行ったときか？」

頂点 \(i\) の値が減少するのは、「頂点 \(i\) 自身、または頂点 \(i\) の子孫（\(i\) の部分木に含まれる頂点）」を選んで操作を行ったときに限られます。

2. 数式で表してみる

頂点 \(i\) を選んで操作を行う回数を \(x_i\) とします。操作回数なので、当然 \(x_i \ge 0\) （非負整数）でなければなりません。

頂点 \(i\) の値が減少する総回数は、最終的に初期水量 \(V_i\) と一致する必要があります。したがって、以下の関係式が成り立ちます。

\[V_i = (\text{頂点 } i \text{ の部分木内の頂点を選んだ回数の総和})\]

ここで、頂点 \(i\) の部分木は「頂点 \(i\) 自身」と「\(i\) の直接の子 \(c\) それぞれの部分木」に分解できます。 よって、上の式は次のように書き換えることができます。

\[V_i = x_i + \sum_{c \in \text{children}(i)} V_c\]

3. 必要十分条件の導出

上の式を変形すると、頂点 \(i\) を選ぶ回数 \(x_i\) は以下のように求まります。

\[x_i = V_i - \sum_{c \in \text{children}(i)} V_c\]

\(x_i \ge 0\) でなければならないため、すべての頂点 \(i\) において以下の条件が成り立つ必要があります。

\[V_i \ge \sum_{c \in \text{children}(i)} V_c\]

実は、この条件がすべての頂点 \(i\) で満たされていることが、すべての水量をちょうど \(0\) にできる必要十分条件になります。

Q. 途中で水量が負にならない順序で操作を行えますか？ 各頂点 \(i\) の値の減少量の累計は、最終的にちょうど \(V_i\) になります。操作はすべて「値を減少させる」操作であるため、最終的な減少量が初期値 \(V_i\) を超えない限り、どのような順番で操作を行っても途中で水量が負（\(0\) 未満）になることはありません。したがって、操作の順番を気にする必要はありません。

アルゴリズム

各頂点 \(i\) について、その「直接の子の初期水量の総和」を計算し、自身の初期水量 \(V_i\) と比較します。

1. 各頂点の子の水量の総和を記録する配列 sum_children（サイズ \(N+1\)、初期値 \(0\)）を用意します。
2. \(2\) から \(N\) までの各頂点 \(i\) について、その親 \(p = P_i\) の sum_children[p] に \(V_i\) を加算します。
3. すべての頂点 \(i\) （\(1 \le i \le N\)）について、 \(V_i < \text{sum\_children}[i]\) となるものが存在するか判定します。
   • \(V_i < \text{sum\_children}[i]\) となる頂点が \(1\) つでもあれば、不可能なため No を出力して終了します。
   • すべての頂点で \(V_i \ge \text{sum\_children}[i]\) が成り立っていれば、 Yes を出力します。

計算量

• 時間計算量: \(O(N)\) 親の配列 \(P\) および初期水量 \(V\) の走査、および各頂点の条件判定はすべて \(O(1)\) で行えるため、全体として \(O(N)\) 時間で処理が完了します。制約 \(N \le 5 \times 10^5\) に対しても十分高速に動作します。

• 空間計算量: \(O(N)\) 入力情報の保持と、各頂点の子の水量の総和を保持する配列 sum_children のために \(O(N)\) のメモリを使用します。

実装のポイント

• 木構造の構築が不要 この問題では、親から子への隣接リストを明示的に構築（グラフ化）する必要はありません。入力で与えられる親の配列 \(P\) を用いて、直接親のインデックスに子の値を足し合わせるだけで「子の水量の総和」を求めることができます。これにより、実装が非常にシンプルになり、実行時間やメモリ使用量も節約できます。

  ソースコード

import sys


def solve():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])

    if N == 1:
        print("Yes")
        return

    # P_2 から P_N までの親情報
    P = [int(x) for x in input_data[1:N]]
    # V_1 から V_N までの初期水量
    V = [int(x) for x in input_data[N : 2 * N]]

    # 各頂点の子の初期水量の総和を記録する配列
    sum_children = [0] * (N + 1)

    for i in range(2, N + 1):
        p = P[i - 2]
        v = V[i - 1]
        sum_children[p] += v

    # 各頂点において、自身の水量が子の水量の総和以上であるか判定
    for i in range(1, N + 1):
        if V[i - 1] < sum_children[i]:
            print("No")
            return

    print("Yes")


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。