Overview

This problem asks us to determine whether we can make all vertex values exactly \(0\) by repeatedly performing the following operation on a rooted tree: “choose a vertex and decrease the value of every vertex on the path from that vertex to the root by \(1\).”

At first glance, this appears to be a complex operation on a tree, but by organizing the properties of the operation, we can reduce it to a very simple condition that only focuses on the relationship between each vertex and its “direct children.”

Analysis

1. Organizing the Rules for Value Decrease

When we choose a vertex \(u\) and perform an operation, the values of all vertices on the path from \(u\) to the root (vertex \(1\)) decrease by \(1\). Let’s reconsider this from the opposite perspective.

“Under what operations does the value of a vertex \(i\) decrease?”

The value of vertex \(i\) decreases only when “vertex \(i\) itself, or a descendant of vertex \(i\) (a vertex contained in the subtree of \(i\))” is chosen for an operation.

2. Expressing This with Equations

Let \(x_i\) denote the number of times vertex \(i\) is chosen for an operation. Since this is a count of operations, naturally \(x_i \ge 0\) (non-negative integer).

The total number of times the value of vertex \(i\) decreases must ultimately equal the initial value \(V_i\). Therefore, the following relation holds:

\[V_i = (\text{total number of times a vertex in the subtree of vertex } i \text{ is chosen})\]

Here, the subtree of vertex \(i\) can be decomposed into “vertex \(i\) itself” and “the subtrees of each direct child \(c\) of \(i\).” Thus, the above equation can be rewritten as:

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

3. Deriving the Necessary and Sufficient Condition

Rearranging the above equation, the number of times vertex \(i\) is chosen, \(x_i\), is determined as:

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

Since \(x_i \ge 0\) must hold, the following condition must be satisfied for all vertices \(i\):

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

In fact, this condition being satisfied for all vertices \(i\) is the necessary and sufficient condition for making all values exactly \(0\).

Q. Can we perform operations in an order that never makes any value negative? The cumulative decrease in the value of each vertex \(i\) ultimately becomes exactly \(V_i\). Since all operations are “decrease” operations, as long as the final total decrease does not exceed the initial value \(V_i\), the value will never become negative (below \(0\)) regardless of the order of operations. Therefore, we do not need to worry about the order of operations.

Algorithm

For each vertex \(i\), compute the “sum of initial values of its direct children” and compare it with its own initial value \(V_i\).

1. Prepare an array sum_children (size \(N+1\), initialized to \(0\)) to record the sum of children’s values for each vertex.
2. For each vertex \(i\) from \(2\) to \(N\), add \(V_i\) to sum_children[p] where \(p = P_i\) is its parent.
3. For all vertices \(i\) (\(1 \le i \le N\)), check whether there exists any vertex where \(V_i < \text{sum\_children}[i]\).
   • If even one vertex satisfies \(V_i < \text{sum\_children}[i]\), it is impossible, so output No and terminate.
   • If \(V_i \ge \text{sum\_children}[i]\) holds for all vertices, output Yes.

Complexity

• Time Complexity: \(O(N)\) Scanning the parent array \(P\) and initial values \(V\), as well as checking the condition for each vertex, can all be done in \(O(1)\) per vertex, so the entire process completes in \(O(N)\) time. This runs sufficiently fast for the constraint \(N \le 5 \times 10^5\).

• Space Complexity: \(O(N)\) \(O(N)\) memory is used for storing the input information and the array sum_children that holds the sum of children’s values for each vertex.

Implementation Notes

• No need to build the tree structure In this problem, there is no need to explicitly construct an adjacency list from parent to children (i.e., build a graph). Using the parent array \(P\) given in the input, we can compute the “sum of children’s values” simply by adding each child’s value directly to its parent’s index. This makes the implementation very simple and also saves execution time and memory usage.

  Source Code

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

---

This editorial was generated by gemini-3.5-flash-thinking.