概要

占領ゲームでは、結局ゲーム対象の都市はすべて占領されます。
したがって問題は「青木君が高橋君の得点を最小にするため、どの部分木を切り落とすか」を考える問題になります。

考察

占領ゲームでは必ず全都市が占領される

ゲーム対象となる木は、根が都市 \(1\) の連結な根付き木です。

最初は都市 \(1\) が占領可能です。
都市が占領されると、その子都市が新たに占領可能になります。

ここで、まだ未占領の都市が残っているとします。
その中で根に最も近い都市を考えると、その親はすでに占領済みです。
したがって、その都市は占領可能です。

つまり、未占領の都市がある限り、必ず占領可能な都市も存在します。
よってゲームは、対象となる木のすべての都市が占領された時点で終了します。

そのため、高橋君と青木君がフェーズ 2 でどの都市を選ぶかは、最終的な集合 \(S\) に影響しません。
最終的な得点は単に「残った木に含まれる都市の価値の総和」になります。

青木君ができること

青木君はフェーズ 1 で、

• 辺を \(1\) 本切る
• または切らない

のどちらかを選べます。

都市 \(i\)（\(i \geq 2\)）とその親を結ぶ辺を切ると、都市 \(i\) を根とする部分木全体がゲーム対象から取り除かれます。

元の全都市の価値の総和を \(total\)、都市 \(i\) を根とする部分木の価値の総和を \(sub_i\) とすると、その辺を切った後の得点は

\( total - sub_i \)

です。

青木君はこの値を最小化したいので、できるだけ大きな \(sub_i\) を持つ部分木を取り除けばよいです。

ただし、辺を切らない選択も可能です。
これは「取り除く価値の総和が \(0\)」と考えられます。

そのため、取り除く価値の最大値は

\( \max(0, sub_2, sub_3, \ldots, sub_N) \)

です。

答えは

\( total - \max(0, sub_2, sub_3, \ldots, sub_N) \)

になります。

素朴な方法ではなぜダメか

フェーズ 2 のゲームを真面目にミニマックスで探索すると、占領順の選び方が非常に多く、指数時間になってしまいます。

また、各辺を切るたびに残った木の総和を毎回計算すると、最悪で \(O(N^2)\) になり、\(N \leq 5 \times 10^5\) では間に合いません。

そこで、各都市を根とする部分木の総和を一度だけ計算します。

アルゴリズム

1. 木を子リストとして構築する。
2. 各都市 \(i\) について、部分木の総和 \(sub_i\) を計算する。
3. \(i = 2, 3, \ldots, N\) について、\(sub_i\) の最大値を求める。
4. 「切らない」場合も考慮するため、最大値の初期値を \(0\) にする。
5. 答えとして \(total - best\_remove\) を出力する。

この問題では親 \(P_i\) が常に \(P_i < i\) を満たします。
つまり、親の番号は子より小さいです。

そのため、都市番号を \(N\) から \(1\) へ逆順に見ていけば、子の部分木和はすでに計算済みになります。

各都市 \(i\) について、

\( sub_i = V_i + \sum_{c: i の子} sub_c \)

として計算できます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

部分木の総和や全体の総和は、値の絶対値が大きいため long long を使います。

また、\(N\) が最大 \(5 \times 10^5\) と大きいので、再帰 DFS を使うとスタックオーバーフローする可能性があります。
今回のコードでは、\(P_i < i\) という性質を利用して、都市番号の逆順に処理することで再帰を使わずに部分木和を計算しています。

best_remove を 0 で初期化している点も重要です。
すべての部分木和が負の場合、どの辺を切っても得点が増えてしまうため、青木君は辺を切らないのが最適になります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

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

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

    vector<long long> sub(N + 1);
    long long total = 0;

    for (int i = N; i >= 1; i--) {
        sub[i] += V[i];
        total += V[i];
        for (int c : children[i]) {
            sub[i] += sub[c];
        }
    }

    long long best_remove = 0;
    for (int i = 2; i <= N; i++) {
        best_remove = max(best_remove, sub[i]);
    }

    cout << total - best_remove << '\n';

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。