概要

この問題は、根付き木における各頂点の水を、指定されたルールに従ってちょうど \(0\) にできるかを判定する問題です。木構造における「祖先と子孫の関係」に着目し、各頂点で行う操作回数を数式で表すことで、非常にシンプルな条件に帰着させることができます。

考察

操作が各頂点に与える影響を整理する

頂点 \(u\) を選んで「排水」操作を \(1\) 回行うと、頂点 \(u\) から根（頂点 \(1\)）までのパス上にあるすべての頂点の水量が \(1\) 減少します。 これを逆に、ある頂点 \(i\) の水量が減少する条件という視点で考えてみましょう。

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

ここで、各頂点 \(u\) を選んで操作を行う回数を \(c_u\) とします。操作回数は \(0\) 以上の整数でなければならないので、\(c_u \ge 0\) です。 頂点 \(i\) の初期水量は \(V_i\) であり、最終的にこれをちょうど \(0\) にしたいので、頂点 \(i\) の水量減少量の合計が \(V_i\) と一致する必要があります。 したがって、各頂点 \(i\) について次の関係式が成り立ちます。

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

（ここで、\(\text{subtree}(i)\) は頂点 \(i\) を根とする部分木に含まれる頂点の集合です。）

部分木の構造を利用して式を簡単にする

頂点 \(i\) の部分木 \(\text{subtree}(i)\) は、頂点 \(i\) 自身と、頂点 \(i\) のすべての子 \(j\) の部分木 \(\text{subtree}(j)\) を合わせたものです。 これを利用して、上の式を次のように分解してみます。

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

ここで、右辺の括弧の中身 \(\sum_{u \in \text{subtree}(j)} c_u\) は、まさに子 \(j\) における水量の式 \(V_j\) そのものです。 したがって、式は以下のように非常にシンプルになります。

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

条件の導出

この式を \(c_i\) について解くと、次のようになります。

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

私たちが求めたいのは、「すべての \(c_i\) が \(0\) 以上の整数となるような操作回数の割り当てが存在するか」です。 \(V_i\) や \(V_j\) はすべて整数であるため、各 \(i\) について \(c_i \ge 0\) が成り立つこと、すなわち、

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

がすべての頂点 \(i\) について成り立つことが、水をちょうど \(0\) にできるための必要十分条件となります。 （葉ノードのように子がいない頂点については、子の水量の総和を \(0\) とみなします。）

アルゴリズム

1. 各頂点 \(i\) について、その「子」の水量の総和を格納する配列 sum_children を用意し、初期値を \(0\) とします。
2. \(2\) から \(N\) までの各頂点 \(i\) について、親 \(P_i\) の sum_children[P_i] に \(V_i\) を加算します。これにより、すべての頂点について「直属の子の水量の総和」を \(O(N)\) で計算できます。
3. すべての頂点 \(i\)（\(1 \le i \le N\)）について、 \(V_i \ge \text{sum\_children}[i]\) が成り立っているかを判定します。
   • もし \(1\) つでも満たさない頂点があれば No を出力します。
   • すべての頂点で満たされていれば Yes を出力します。

計算量

• 時間計算量: \(O(N)\) 親の配列 \(P\) や水量の配列 \(V\) の入力、および各頂点の子の水量の足し合わせ、最終判定のすべてをループ \(1\) 回（\(O(N)\)）で行うことができるため、十分に高速です。
• 空間計算量: \(O(N)\) 頂点ごとの情報を管理するために vector を数個使用するのみであるため、メモリ制限にも余裕で間に合います。

実装のポイント

• オーバーフローへの対策: 各頂点の水量 \(V_i\) は最大で \(10^9\) です。子の水量の総和を計算する際、合計値が 32bit 整数の最大値（約 \(2 \times 10^9\)）を超える可能性があるため、sum_children や V を格納する型には long long（64bit 整数）を使用する必要があります。

  ソースコード

#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;
}

---

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