概要

各社員（頂点）について「直属の部下の部分木仕事量の最大値 − 最小値」を求め、その最大値（組織全体のアンバランス度）を計算する問題です。部分木の仕事量（部分木和）を全頂点で効率よく求めるのがポイントです。

考察

重要な気づき

• 「社員 \(u\) が率いるチームの仕事量」は、\(u\) を根とする部分木の総和（部分木和）です。
• 社員 \(v\) のアンバランス度は、\(v\) の直属の部下それぞれの部分木和を集めて、
  \( \max - \min \) を取ったものです（部下が \(0\) 人や \(1\) 人なら \(0\)）。

したがって必要なのは、 1. 各頂点 \(i\) の部分木和 \(sub[i]\) 2. 各頂点 \(v\) について、子（直属の部下）の \(sub[\text{child}]\) の最小値・最大値

です。

素朴な方法が厳しい理由

• 各頂点ごとに「その子の部分木和」を計算するために毎回 DFS すると、最悪 \(O(N^2)\) になります。
• 木全体で一度 DFS して部分木和を求め、各頂点で子の最大・最小を取るなら \(O(N)\) ですが、Python では再帰 DFS は深さが最大 \(2\times 10^5\) になり得て、再帰制限やスタックの問題が出やすいです。

どう解決するか

この問題では入力制約 \(P_i \le i-1\) があり、親の番号が必ず子より小さいです。
つまり番号の大きい頂点ほど葉側にあり、i = N, N-1, ..., 1 の逆順に処理すれば、自然に「子→親」へ部分木和を集計できます（再帰不要）。

アルゴリズム

以下を配列で管理し、頂点を \(N\) から \(1\) へ逆順に処理します。

• sub[i]：頂点 \(i\) の部分木和（初期値は \(W_i\)）
• minc[i]：頂点 \(i\) の子部分木和の最小値
• maxc[i]：頂点 \(i\) の子部分木和の最大値
• cnt[i]：頂点 \(i\) の子の数（直属の部下の人数）

処理手順（逆順に i を走査）： 1. もし cnt[i] >= 2 なら、頂点 \(i\) のアンバランス度は maxc[i] - minc[i]。答え ans を更新する。 2. \(i \ge 2\) のとき、親 \(p = P_i\) に対して - sub[p] += sub[i]（部分木和を親へ加算） - minc[p] = min(minc[p], sub[i]) - maxc[p] = max(maxc[p], sub[i]) - cnt[p] += 1

これで、各子の部分木和が親にちょうど1回ずつ反映され、全頂点のアンバランス度の最大値が求まります。

例：ある頂点 \(v\) の子が \(a,b,c\) で、それぞれの部分木和が \(10, 25, 18\) なら
アンバランス度は \(25-10=15\) です。これを全頂点での最大として出力します。

計算量

• 時間計算量: \(O(N)\)（各頂点を1回処理し、親への更新も1回）
• 空間計算量: \(O(N)\)（sub, minc, maxc, cnt, parent などの配列）

実装のポイント

• minc の初期値は十分大きい値（例：INF = 10**30）、maxc は十分小さい値で初期化しておくと更新が簡単です。

• 部下が \(1\) 人以下のときアンバランス度は \(0\) なので、cnt[i] >= 2 のときだけ差を計算します。

• 入力が大きいので、sys.stdin.buffer.read() でまとめて読み取ると高速です。

• 再帰を使わず、P_i < i を利用して逆順に集計するのがこの解法の肝です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    idx = 0
    N = data[idx]
    idx += 1

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

    w = [0] * (N + 1)
    for i in range(1, N + 1):
        w[i] = data[idx]
        idx += 1

    INF = 10**30
    sub = w[:]  # subtree sums
    minc = [INF] * (N + 1)
    maxc = [-INF] * (N + 1)
    cnt = [0] * (N + 1)

    ans = 0
    for i in range(N, 0, -1):
        if cnt[i] >= 2:
            diff = maxc[i] - minc[i]
            if diff > ans:
                ans = diff
        if i >= 2:
            p = parent[i]
            si = sub[i]
            sub[p] += si
            if si < minc[p]:
                minc[p] = si
            if si > maxc[p]:
                maxc[p] = si
            cnt[p] += 1

    print(ans)

if __name__ == "__main__":
    main()

---

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