概要

この問題は、木構造の道路網に沿って水路を整備する際、各道路の工事をどちらの端点（集落）に担当させるかを最適に決定し、発生する追加コストを最小化する問題です。

木構造の性質を利用し、葉（末端の集落）から根（中心地）に向かって状態を決めていく木DP（木上の動的計画法）を用いることで、効率良く解くことができます。

---

考察

1. 意思決定の構造

各道路（辺）は、それが結ぶ \(2\) つの集落のどちらか一方のみが担当します。 木構造において、ある集落 \(i\)（根以外）に着目すると、関係する道路は以下の \(2\) 種類に分類できます。 1. 親集落 \(P_i\) と結ぶ道路（\(1\) 本） 2. 子集落と結ぶ道路（\(0\) 本以上）

集落 \(i\) を根とする部分木において、最適な割り当てを考えます。このとき、親集落 \(P_i\) との間の道路を「親が担当するか」「子（集落 \(i\)）が担当するか」によって、集落 \(i\) の状況が変わります。

そこで、以下のように \(2\) つの状態を持つDP（動的計画法）を定義します。

• \(\text{dp0}[i]\) : 親との間の道路を親 \(P_i\) が担当するとしたときの、部分木 \(i\) における追加コストの最小値。
  • このとき、集落 \(i\) が担当する道路は「子集落との間の道路」のみです。
• \(\text{dp1}[i]\) : 親との間の道路を子 \(i\) が担当するとしたときの、部分木 \(i\) における追加コストの最小値。
  • このとき、集落 \(i\) が担当する道路は「子集落との間の道路」に加えて「親との間の道路（\(1\) 本）」となります。

2. 子集落との割り当ての最適化

集落 \(i\) の子集落を \(v_1, v_2, \ldots, v_k\) とします。 集落 \(i\) と各子集落 \(v\) を結ぶ道路について、どちらが担当するかを決めます。

• 子集落 \(v\) が担当する場合：部分木 \(v\) の追加コストは \(\text{dp1}[v]\) となります。
• 集落 \(i\) が担当する場合：部分木 \(v\) の追加コストは \(\text{dp0}[v]\) となります。また、集落 \(i\) の担当数が \(1\) 増えます。

子集落 \(v\) との間の道路を「子 \(v\) 担当」から「集落 \(i\) 担当」に切り替えたとき、部分木 \(v\) 側で発生するコストの差分は \(\text{dp0}[v] - \text{dp1}[v]\) となります。

集落 \(i\) が子集落との道路のうち \(x\) 本（\(0 \leq x \leq k\)）を担当すると決めたとき、コストを最小化するためには、差分 \(\text{dp0}[v] - \text{dp1}[v]\) が小さい子集落から優先して \(x\) 個選んで集落 \(i\) 担当にするのが最適です。

3. 具体的な遷移

すべての子集落について、差分 \(D_v = \text{dp0}[v] - \text{dp1}[v]\) を計算し、昇順にソートします。 ソートされた差分の累積和を \(S\) とします（\(S[x]\) は差分が小さい方から \(x\) 個選んだときの総和）。

集落 \(i\) が子集落との道路を \(x\) 本担当するときのコストは、以下のように表せます。

• \(\text{dp0}[i]\) の場合（親が担当） 集落 \(i\) の担当数は \(x\) 本です。 $\(\text{Cost} = \sum_{v} \text{dp1}[v] + S[x] + W_i \times \max(0, x - C_i)\)$

• \(\text{dp1}[i]\) の場合（子 \(i\) が担当） 集落 \(i\) の担当数は \(x + 1\) 本（親との間の道路を含む）です。 $\(\text{Cost} = \sum_{v} \text{dp1}[v] + S[x] + W_i \times \max(0, x + 1 - C_i)\)$

\(x\) を \(0\) から \(k\) まで全探索し、それぞれの最小値を求めることで \(\text{dp0}[i]\) と \(\text{dp1}[i]\) を決定できます。

---

アルゴリズム

1. グラフの構築: 各集落の親子の関係を記録します。制約 \(P_i \leq i - 1\) より、頂点番号の大きい順（\(N\) から \(1\)）にループを回すだけで、トポロジカルソートやDFS（深さ優先探索）をすることなく、自動的に葉から根へのボトムアップな順序で処理できます。

2. 葉から順にDP値を計算: 各集落 \(i\) について：

   • 子集落の DP 値から差分配列 diffs（\(\text{dp0}[v] - \text{dp1}[v]\)）を作成し、昇順にソートします。
   • diffs の累積和 \(S\) を計算します。
   • \(x \in [0, k]\) の範囲で全探索し、\(\text{dp0}[i]\) と \(\text{dp1}[i]\) の最小値を求めます。

3. 答えの出力: 根（集落 \(1\)）には親がいないため、求める最小追加コストは \(\text{dp0}[1]\) です。これに基本工事コスト \(N - 1\) を足したものが全体の最小総コストになります。

---

計算量

• 時間計算量: \(O(N \log N)\) 各集落 \(i\) において、子の個数を \(k_i\) とすると、差分配列のソートに \(O(k_i \log k_i)\) の時間がかかります。すべての集落における子の総和は \(N - 1\) であるため、全体のソートにかかる時間の合計は最悪でも \(O(N \log N)\) となり、実行時間制限に十分間に合います。

• 空間計算量: \(O(N)\) 木構造の隣接リスト、DPテーブル（dp0, dp1）、および各ステップで用いる一時的な配列（diffs や累積和）を保持するために必要なメモリは \(O(N)\) です。

---

実装のポイント

• 型に注意: 追加コスト係数 \(W_i\) が最大 \(10^9\) であり、総コストは int 型（32bit整数）の範囲を容易に超えるため、DPテーブルや累積和の計算には long long 型（64bit整数）を使用する必要があります。

• 無限大の初期値: 最小値を求める際の初期値（INF）は、十分大きな値（4e18 など）に設定してください。

• ボトムアップ処理の簡略化: 制約の \(P_i < i\) を利用し、for (int i = N; i >= 1; --i) と逆順ループを回すだけで、簡潔かつ高速に葉から根への遷移を実装できます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

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

    // dp0[i] corresponds to dp[i][0]
    // dp1[i] corresponds to dp[i][1]
    vector<long long> dp0(N + 1, 0), dp1(N + 1, 0);

    // Process bottom-up from leaves to root
    for (int i = N; i >= 1; --i) {
        int k = children[i].size();
        vector<long long> diffs;
        diffs.reserve(k);
        long long sum_dp1 = 0;
        for (int child : children[i]) {
            sum_dp1 += dp1[child];
            diffs.push_back(dp0[child] - dp1[child]);
        }
        sort(diffs.begin(), diffs.end());
        
        vector<long long> S(k + 1, 0);
        for (int j = 0; j < k; ++j) {
            S[j + 1] = S[j] + diffs[j];
        }

        long long min0 = 4e18; // Use a sufficiently large value for infinity
        long long min1 = 4e18;
        for (int x = 0; x <= k; ++x) {
            long long val0 = S[x] + W[i] * max(0LL, (long long)x - C[i]);
            if (val0 < min0) min0 = val0;
            long long val1 = S[x] + W[i] * max(0LL, (long long)x + 1 - C[i]);
            if (val1 < min1) min1 = val1;
        }
        dp0[i] = sum_dp1 + min0;
        dp1[i] = sum_dp1 + min1;
    }

    // The total cost is the minimum additional cost at the root + the base cost (N - 1)
    long long ans = dp0[1] + (N - 1);
    cout << ans << "\n";

    return 0;
}

---

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