概要

根付き木の各ノードの水量を、パスに沿った減少操作で全て \(0\) にできるか判定する問題。各ノードについて「自分の水量が子ノードの水量の合計以上」であることが必要十分条件となる。

考察

操作の言い換え

ノード \(u\) を選ぶ操作は、\(u\) から根までのパス上の全ノードを \(1\) 減らします。ここで、各ノード \(u\) を選ぶ回数を \(x[u]\)（\(x[u] \geq 0\)）と定義しましょう。

あるノード \(v\) が減少する総量を考えると、\(v\) を通る操作は「\(v\) の部分木に属するノード \(u\) を選んだとき」に限られます。よって、ノード \(v\) の総減少量は：

\[S[v] = \sum_{u \in \text{subtree}(v)} x[u]\]

全ノードの水量を \(0\) にするには \(S[v] = V[v]\) が必要です。

必要十分条件の導出

\(S[v]\) は次のように分解できます：

\[S[v] = x[v] + \sum_{c \in \text{children}(v)} S[c]\]

\(S[v] = V[v]\) かつ \(S[c] = V[c]\) を代入すると：

\[x[v] = V[v] - \sum_{c \in \text{children}(v)} V[c]\]

\(x[v]\) は操作回数なので \(x[v] \geq 0\) が必要です。したがって：

\[V[v] \geq \sum_{c \in \text{children}(v)} V[c]\]

が全ノード \(v\) について成り立つことが必要です。

操作順序の実現可能性

上記条件が十分であることも示せます。ボトムアップ順（葉から根に向かう順）で操作を行えば、途中でどのノードも負になりません。

• 葉ノード \(u\) について \(x[u]\) 回操作すると、\(u\) から根へのパス上の各ノードが減少しますが、各ノード \(v\) の最終的な減少量は \(V[v]\) に等しくなるよう設計されています。
• ボトムアップ順で処理するとき、ノード \(v\) の時点で既に子の部分木からの操作で \(\sum_{c} V[c]\) だけ減っており、残りはちょうど \(x[v] = V[v] - \sum_c V[c] \geq 0\) です。

アルゴリズム

1. 木構造を読み込む。
2. 各ノード \(v\) について、子ノードの \(V\) 値の合計を計算する。
3. 全ノード \(v\) に対して \(V[v] \geq \sum_{c \in \text{children}(v)} V[c]\) を確認する。
4. 全て満たせば Yes、そうでなければ No を出力する。

具体例

木が 1 → 2 → 3 で \(V = [5, 3, 2]\) の場合： - ノード \(3\)（葉）：子なし → \(2 \geq 0\) ✓ - ノード \(2\)：子は \(3\) → \(3 \geq 2\) ✓ - ノード \(1\)：子は \(2\) → \(5 \geq 3\) ✓

\(x[3] = 2, x[2] = 1, x[1] = 2\) で全て \(0\) にできます。

計算量

• 時間計算量: \(O(N)\)（各ノードを一度ずつ走査）
• 空間計算量: \(O(N)\)（木構造と水量の保持）

実装のポイント

• 再帰を使わず、単純に各ノード \(i\)（\(2 \leq i \leq N\)）について child_sum[parent[i]] += V[i] と加算するだけで子の合計が求まる。

• \(N = 1\) の場合は子が存在しないため、\(V[1] \geq 0\) で常に Yes（\(V[1] = 0\) なら操作不要、\(V[1] > 0\) ならノード \(1\) を \(V[1]\) 回選ぶ）。

• \(V\) の値が最大 \(10^9\) で子が多数あり得るため、合計値のオーバーフローに注意（Python では問題なし）。

  ソースコード

import sys
from sys import setrecursionlimit

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    
    for i in range(2, N + 1):
        p = int(input_data[idx]); idx += 1
        parent[i] = p
        children[p].append(i)
    
    V = [0] * (N + 1)
    for i in range(1, N + 1):
        V[i] = int(input_data[idx]); idx += 1
    
    # Each operation picks a node u and decrements all nodes on path from u to root by 1.
    # Let x[u] = number of times we pick node u. x[u] >= 0.
    # For each node v, the total decrement is sum of x[u] for all u in subtree of v.
    # Let S[v] = sum of x[u] for u in subtree(v). Then S[v] = V[v] for all v.
    # Also S[v] = x[v] + sum_{c child of v} S[c] = x[v] + sum_{c child of v} V[c]... 
    # Wait, S[v] = x[v] + sum of S[c] for c in children(v).
    # So x[v] = S[v] - sum_{c in children(v)} S[c] = V[v] - sum_{c in children(v)} V_subtotal[c]
    # Wait, S[v] must equal V[v].
    # So x[v] = V[v] - sum_{c in children(v)} S[c] = V[v] - sum_{c in children(v)} V[c]... 
    # No. S[c] = V[c] (the requirement for node c). So:
    # x[v] = V[v] - sum_{c in children(v)} V[c]
    # Wait, that's not right either. S[v] is the sum of x[u] over all u in subtree of v.
    # S[v] = x[v] + sum_{c child of v} S[c].
    # We need S[v] = V[v] for each v.
    # So x[v] = V[v] - sum_{c child of v} S[c] = V[v] - sum_{c child of v} V[c].
    # Wait no: S[c] = V[c], so x[v] = V[v] - sum_{c child of v} V[c].
    # Hmm, but V[c] here is the value at node c, not the subtree sum.
    # Let me re-check. S[v] = sum of x[u] for u in subtree(v). The constraint is S[v] = V[v].
    # S[v] = x[v] + sum_{c in children(v)} S[c] = x[v] + sum_{c in children(v)} V[c].
    # So x[v] = V[v] - sum_{c in children(v)} V[c].
    # But wait, V[c] here is the *original* water at node c, and S[c] = V[c].
    # Hmm, actually S[c] should be the number of operations that pass through c, which equals V[c].
    # And S[v] = x[v] + sum of S[c] for children c. So yes, x[v] = V[v] - sum_{c} V[c].
    # Wait, that doesn't seem right for deeper trees. S[c] = V[c] means the subtree sum of x 
    # below c equals V[c], not that V[c] is the only contribution.
    # Actually S[c] = V[c] by the constraint. So regardless of depth:
    # x[v] = S[v] - sum_{c child of v} S[c] = V[v] - sum_{c child of v} V[c].
    
    # But we also need the ordering constraint: at no point does any node go negative.
    # However, the ordering constraint is automatically satisfiable if x[v] >= 0 for all v.
    # Because we can process in bottom-up order (leaves first), and each operation from u 
    # decreases ancestors. If we do leaves first, by the time we process v, its children 
    # subtrees are done, and v has exactly x[v] remaining which we drain by picking v itself.
    # Since operations decrease ancestors too, we need V[v] to be enough. But in bottom-up 
    # order it works out because S[v] = V[v] exactly.
    
    # So the answer is Yes iff for all v: V[v] >= sum of V[c] for children c of v.
    
    # Compute sum of children's V for each node
    child_sum = [0] * (N + 1)
    for i in range(2, N + 1):
        child_sum[parent[i]] += V[i]
    
    possible = True
    for v in range(1, N + 1):
        if V[v] < child_sum[v]:
            possible = False
            break
    
    print("Yes" if possible else "No")

main()

---

この解説は claude4.6opus-thinking によって生成されました。