概要

この問題は、木構造で表される組織において、各管理職の直属の部下チームの仕事量の最大値と最小値の差（アンバランス度）の最大値を求める問題です。

考察

組織は根付き木で表され、社員1が根（社長）となります。重要な観察点は： - 一般社員（葉ノード）のみが実際の仕事量を持ち、管理職（内部ノード）の仕事量は0です - ある社員のアンバランス度は、その直属の部下たちが率いるチームの仕事量の最大値と最小値の差で定義されます - 部下が1人以下の場合、アンバランス度は0になります

素朴なアプローチでは、各ノードに対して部分木の仕事量を再計算すると、時間計算量が \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) に対して遅すぎます。効率的に計算するためには、ボトムアップ（葉から根へ）のアプローチが必要です。

アルゴリズム

1. 木の構築: 入力から隣接リストを作成します
2. DFS順序の決定: スタックを使って深さ優先探索の順序（帰りがけ順）を決定します
3. ボトムアップ計算:
   • 葉ノード：そのノードの仕事量を部分木の仕事量とします
   • 内部ノード：すべての子ノードの部分木仕事量の和を計算します
   • 部下が2人以上いる場合、部下チームの仕事量の最大値と最小値の差を計算し、答えを更新します

このアプローチでは、各ノードを1回ずつ処理するため効率的です。

計算量

• 時間計算量: \(O(N)\) - 各ノードを1回ずつ処理します
• 空間計算量: \(O(N)\) - グラフの表現と作業用配列に線形メモリを使用します

実装のポイント

• スタックを使った反復的DFSで再帰の深さ制限を回避

• 帰りがけ順をリストに保存してから逆順に処理

• 子ノードの仕事量リストを集計しながら、同時にアンバランス度を計算

• 部下が1人以下の場合はスキップして計算コストを節約

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    P_list = list(map(int, data[1:1+n-1]))
    W_list = list(map(int, data[1+n-1:1+n-1+n]))
    
    graph = [[] for _ in range(n+1)]
    for i in range(2, n+1):
        p = P_list[i-2]
        graph[p].append(i)
    
    total_work = [0] * (n+1)
    ans = 0
    
    stack = [1]
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        for v in graph[u]:
            stack.append(v)
    
    for u in reversed(order):
        if not graph[u]:
            total_work[u] = W_list[u-1]
        else:
            child_works = []
            for v in graph[u]:
                total_work[u] += total_work[v]
                child_works.append(total_work[v])
            
            if len(child_works) >= 2:
                max_val = max(child_works)
                min_val = min(child_works)
                ans = max(ans, max_val - min_val)
    
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。