概要

占領ゲームでは、どのようにプレイしても対象となった木の全都市が最終的に占領されます。
したがって、青木君はフェーズ 1 で「合計価値が最も大きい部分木」を取り除くのが最適です。

考察

占領ゲームで最終的に占領される都市

フェーズ 2 では、占領可能な都市を必ず 1 つ占領しなければならず、パスはできません。

対象となるグラフは根付き木であり、根である都市 \(1\) は最初から占領可能です。

ここで重要なのは、対象となる木に未占領の都市が残っている限り、必ず占領可能な都市も存在するということです。

なぜなら、未占領の都市 \(x\) を 1 つ選び、根から \(x\) までのパスを考えると、そのパス上で「すでに占領済みの都市の直後にある未占領の都市」が存在します。
その都市は親が占領済みなので、占領可能です。

よって、ゲームは対象となる木の全都市が占領されたときに終了します。

つまり、フェーズ 2 でのプレイヤーの選択順は最終的な合計値に影響しません。

---

フェーズ 1 で青木君ができること

青木君は辺を 1 本封鎖するか、何もしないことができます。

辺 \((P_i, i)\) を封鎖すると、都市 \(1\) を含まない側は、都市 \(i\) を根とする部分木になります。

したがって、そのとき最終的に得られる合計値は

\(全体の合計 - 都市 i の部分木の合計\)

です。

青木君はこの値を最小化したいので、できるだけ大きい部分木の合計を取り除きたいです。

ただし、部分木の合計が負の場合、それを取り除くと逆に合計値が増えてしまいます。
そのため、すべての部分木の合計が \(0\) 以下なら、青木君は何も封鎖しないのが最適です。

よって答えは

\(全体の合計 - \max(0, 根以外の各都市を根とする部分木の合計の最大値)\)

となります。

---

素朴な方法ではなぜ難しいか

フェーズ 2 を通常のゲームとして考え、各手番で選べる都市を列挙して minimax を行うと、選択肢が非常に多くなり、指数時間になってしまいます。

また、各辺を封鎖した場合について毎回 DFS などで部分木の合計を求めると、最悪で \(O(N^2)\) かかります。
\(N \leq 5 \times 10^5\) なので、これは間に合いません。

そこで、各都市を根とする部分木の合計を一度の後ろ向き処理で求めます。

アルゴリズム

1. 各都市の部分木の合計を管理する配列 sub を用意し、最初は sub[i] = V_i とする。
2. 都市番号を \(N\) から \(2\) まで逆順に見る。
   • 制約より \(P_i < i\) なので、親は必ず子より小さい番号である。
   • そのため、逆順に処理すれば、都市 \(i\) の子孫たちはすでに sub[i] に足し込まれている。
3. 各都市 \(i\) について、
   • sub[i] を「取り除ける部分木の合計」の候補として見る。
   • その最大値を best に記録する。
   • sub[i] を親 P_i に足す。
4. 最後に sub[1] が木全体の合計になる。
5. 答えは sub[1] - best。
   • best の初期値を \(0\) にしておくことで、「何も封鎖しない」場合も自然に扱える。

例えば、ある部分木の合計が \(10\) なら、それを取り除くと最終合計は \(10\) 減ります。
一方、最大の部分木合計が負なら、取り除くメリットがないため best = 0 のままになり、全体の合計が答えになります。

計算量

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

実装のポイント

P_i < i という条件があるため、隣接リストを作って DFS する必要はありません。
都市番号を大きい順に処理すれば、各都市の部分木和を親に足し上げるだけで求められます。

また、値 \(V_i\) は最大で \(10^9\)、都市数は最大で \(5 \times 10^5\) なので、合計値は 32 bit 整数に収まりません。
Python では整数のオーバーフローを気にする必要はありませんが、他言語では 64 bit 整数を使う必要があります。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    v = [0] + data[1:1+n]

    if n == 1:
        print(v[1])
        return

    parents = [0] * (n + 1)
    idx = 1 + n
    for i in range(2, n + 1):
        parents[i] = data[idx]
        idx += 1

    sub = v[:]
    best = 0

    for i in range(n, 1, -1):
        s = sub[i]
        if s > best:
            best = s
        sub[parents[i]] += s

    print(sub[1] - best)

if __name__ == "__main__":
    main()

---

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