Overview

This problem asks whether we can reduce the water volume at each node of a rooted tree to \(0\) using decrease operations along paths. The necessary and sufficient condition is that for each node, “its water volume is at least the sum of its children’s water volumes.”

Analysis

Rephrasing the Operation

Choosing a node \(u\) decreases all nodes on the path from \(u\) to the root by \(1\). Let us define \(x[u]\) (\(x[u] \geq 0\)) as the number of times node \(u\) is chosen.

Considering the total amount by which a node \(v\) is decreased, the operations that pass through \(v\) are limited to “when a node \(u\) belonging to the subtree of \(v\) is chosen.” Therefore, the total decrease for node \(v\) is:

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

To make all nodes’ water volumes \(0\), we need \(S[v] = V[v]\).

Deriving the Necessary and Sufficient Condition

\(S[v]\) can be decomposed as follows:

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

Substituting \(S[v] = V[v]\) and \(S[c] = V[c]\):

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

Since \(x[v]\) represents the number of operations, we need \(x[v] \geq 0\). Therefore:

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

must hold for all nodes \(v\).

Feasibility of Operation Order

We can also show that the above condition is sufficient. By performing operations in bottom-up order (from leaves toward the root), no node becomes negative during the process.

• When we perform the operation \(x[u]\) times for a leaf node \(u\), each node on the path from \(u\) to the root is decreased, and the final decrease for each node \(v\) is designed to equal \(V[v]\).
• When processing in bottom-up order, at node \(v\), the operations from child subtrees have already decreased it by \(\sum_{c} V[c]\), and the remainder is exactly \(x[v] = V[v] - \sum_c V[c] \geq 0\).

Algorithm

1. Read the tree structure.
2. For each node \(v\), compute the sum of the \(V\) values of its children.
3. For all nodes \(v\), verify that \(V[v] \geq \sum_{c \in \text{children}(v)} V[c]\).
4. If all conditions are satisfied, output Yes; otherwise, output No.

Concrete Example

For a tree 1 → 2 → 3 with \(V = [5, 3, 2]\): - Node \(3\) (leaf): no children → \(2 \geq 0\) ✓ - Node \(2\): child is \(3\) → \(3 \geq 2\) ✓ - Node \(1\): child is \(2\) → \(5 \geq 3\) ✓

With \(x[3] = 2, x[2] = 1, x[1] = 2\), all values can be reduced to \(0\).

Complexity

• Time complexity: \(O(N)\) (traversing each node once)
• Space complexity: \(O(N)\) (storing the tree structure and water volumes)

Implementation Notes

• Without using recursion, the sum of children can be computed simply by adding child_sum[parent[i]] += V[i] for each node \(i\) (\(2 \leq i \leq N\)).

• When \(N = 1\), there are no children, so \(V[1] \geq 0\) always holds and the answer is Yes (if \(V[1] = 0\), no operation is needed; if \(V[1] > 0\), choose node \(1\) exactly \(V[1]\) times).

• Since \(V\) values can be up to \(10^9\) and a node can have many children, be careful about overflow in the sum (this is not an issue in Python).

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.