Overview

This problem asks us to determine whether it is possible to reduce the water at each vertex in a rooted tree to exactly \(0\) following specified rules. By focusing on the “ancestor-descendant relationship” in the tree structure and expressing the number of operations performed at each vertex as a formula, we can reduce the problem to a very simple condition.

Analysis

Organizing the effect of operations on each vertex

When we select vertex \(u\) and perform one “drain” operation, the water amount decreases by \(1\) for all vertices on the path from vertex \(u\) to the root (vertex \(1\)). Let’s think about this from the reverse perspective: under what conditions does the water amount at a given vertex \(i\) decrease?

The water amount at vertex \(i\) decreases when we perform an operation by selecting “vertex \(i\) itself, or a descendant of vertex \(i\) (a vertex contained in the subtree of \(i\)).”

Here, let \(c_u\) denote the number of times we select vertex \(u\) to perform the operation. Since the number of operations must be a non-negative integer, \(c_u \ge 0\). The initial water amount at vertex \(i\) is \(V_i\), and we want to make it exactly \(0\) in the end, so the total decrease in water at vertex \(i\) must equal \(V_i\). Therefore, the following relation holds for each vertex \(i\):

\[V_i = \sum_{u \in \text{subtree}(i)} c_u\]

(Here, \(\text{subtree}(i)\) is the set of vertices contained in the subtree rooted at vertex \(i\).)

Simplifying the formula using subtree structure

The subtree \(\text{subtree}(i)\) of vertex \(i\) consists of vertex \(i\) itself combined with the subtrees \(\text{subtree}(j)\) of all children \(j\) of vertex \(i\). Using this, we can decompose the above formula as follows:

\[V_i = c_i + \sum_{j \in \text{children}(i)} \left( \sum_{u \in \text{subtree}(j)} c_u \right)\]

Here, the content inside the parentheses on the right side, \(\sum_{u \in \text{subtree}(j)} c_u\), is exactly the water formula \(V_j\) for child \(j\). Therefore, the formula simplifies to:

\[V_i = c_i + \sum_{j \in \text{children}(i)} V_j\]

Deriving the condition

Solving this formula for \(c_i\), we get:

\[c_i = V_i - \sum_{j \in \text{children}(i)} V_j\]

What we want to determine is “whether there exists an assignment of operation counts such that all \(c_i\) are non-negative integers.” Since \(V_i\) and \(V_j\) are all integers, the condition is that \(c_i \ge 0\) holds for each \(i\), namely:

\[V_i \ge \sum_{j \in \text{children}(i)} V_j\]

must hold for all vertices \(i\). This is the necessary and sufficient condition for being able to reduce all water to exactly \(0\). (For leaf nodes that have no children, the sum of children’s water amounts is considered to be \(0\).)

Algorithm

1. For each vertex \(i\), prepare an array sum_children to store the sum of water amounts of its children, initialized to \(0\).
2. For each vertex \(i\) from \(2\) to \(N\), add \(V_i\) to sum_children[P_i] of its parent \(P_i\). This allows us to compute the “sum of water amounts of direct children” for all vertices in \(O(N)\).
3. For all vertices \(i\) (\(1 \le i \le N\)), check whether \(V_i \ge \text{sum\_children}[i]\) holds.
   • If even one vertex does not satisfy this, output No.
   • If all vertices satisfy it, output Yes.

Complexity

• Time complexity: \(O(N)\) Reading the parent array \(P\) and water amount array \(V\), summing up children’s water amounts for each vertex, and the final check can all be done in a single loop (\(O(N)\)), making it sufficiently fast.
• Space complexity: \(O(N)\) We only use a few vectors to manage per-vertex information, so it easily fits within the memory limit.

Implementation Notes

• Overflow prevention: The water amount \(V_i\) at each vertex can be up to \(10^9\). When computing the sum of children’s water amounts, the total may exceed the maximum value of a 32-bit integer (approximately \(2 \times 10^9\)), so long long (64-bit integer) must be used for the types storing sum_children and V.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> P(N + 1);
    for (int i = 2; i <= N; ++i) {
        cin >> P[i];
    }

    vector<long long> V(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> V[i];
    }

    vector<long long> sum_children(N + 1, 0);
    for (int i = 2; i <= N; ++i) {
        sum_children[P[i]] += V[i];
    }

    bool possible = true;
    for (int i = 1; i <= N; ++i) {
        if (V[i] < sum_children[i]) {
            possible = false;
            break;
        }
    }

    if (possible) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

---

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