概要

木構造の家系図において、各人物から根（始祖）までの経路上にある遺産の合計を求める問題です。前処理で全員の累積遺産を計算しておくことで、各クエリに \(O(1)\) で答えられます。

考察

素朴なアプローチとその問題点

各クエリごとに、指定された人物 \(X\) から親を辿って根まで移動し、経路上の遺産を足し合わせる方法が考えられます。

しかし、この方法では： - 最悪の場合、木の深さが \(O(N)\) になる（一直線の木の場合） - クエリが \(Q\) 個あるので、全体で \(O(N \times Q)\) の計算量 - \(N, Q \leq 2 \times 10^5\) なので、最大 \(4 \times 10^{10}\) 回の操作が必要となり、TLE（時間制限超過）になります

重要な気づき

ある人物 \(i\) の累積遺産を \(cumsum[i]\) とすると、以下の関係が成り立ちます：

\[cumsum[i] = cumsum[P_i] + V_i\]

つまり、親の累積遺産に自分の遺産を足すだけで計算できます。

例えば、以下のような木を考えます：

    1 (遺産: 100)
    |
    2 (遺産: 50)
   / \
  3   4
(30) (20)

• \(cumsum[1] = 100\)（根は自分の遺産のみ）
• \(cumsum[2] = cumsum[1] + 50 = 150\)
• \(cumsum[3] = cumsum[2] + 30 = 180\)
• \(cumsum[4] = cumsum[2] + 20 = 170\)

アルゴリズム

1. 前処理として各人物の子リストを作成

   • 親から子への辺を管理することで、根から順に探索できるようにする

2. BFS（幅優先探索）で累積遺産を計算

   • 根（人物1）から開始し、\(cumsum[1] = V_1\) と初期化
   • キューを使って、親から子へと順番に処理
   • 各子について、\(cumsum[child] = cumsum[parent] + V_{child}\) を計算

3. クエリ処理

   • 前処理で計算した \(cumsum\) 配列を参照するだけ
   • 各クエリは \(O(1)\) で回答可能

計算量

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

  • 前処理（BFS）: 各人物を1回ずつ処理するので \(O(N)\)
  • クエリ処理: 各クエリは配列参照のみで \(O(1)\)、\(Q\) 個あるので \(O(Q)\)

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

  • 累積遺産配列 \(cumsum\): \(O(N)\)
  • 子リスト \(children\): 辺の数が \(N-1\) なので \(O(N)\)
  • BFSのキュー: 最大 \(O(N)\)

実装のポイント

1. インデックスのずれに注意

   • 人物番号は \(1\) から \(N\)（1-indexed）
   • 遺産の配列 \(V\) は \(0\) から \(N-1\)（0-indexed）
   • V[i-1] で人物 \(i\) の遺産を取得

2. \(N = 1\) の場合の処理

   • 親の情報が存在しない（人物1には親がいない）
   • 空行を読み飛ばす処理が必要

3. 出力の効率化

   • 結果をリストに溜めて最後にまとめて出力することで、I/Oのオーバーヘッドを削減

   • '\n'.join(map(str, results)) で高速に出力

     ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    
    N, Q = map(int, input().split())
    V = list(map(int, input().split()))
    
    if N >= 2:
        P = [0, 0] + list(map(int, input().split()))
    else:
        P = [0, 0]
        input()  # 空行を読む
    
    # 累積遺産を計算する
    # cumsum[i] = 人物iから根(人物1)までの遺産の合計
    cumsum = [0] * (N + 1)
    
    # BFSで根から順に計算
    # 子のリストを作成
    children = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        children[P[i]].append(i)
    
    # BFSで累積遺産を計算
    cumsum[1] = V[0]  # V[0]は人物1の遺産
    queue = deque([1])
    
    while queue:
        node = queue.popleft()
        for child in children[node]:
            cumsum[child] = cumsum[node] + V[child - 1]  # V[child-1]は人物childの遺産
            queue.append(child)
    
    # クエリに答える
    results = []
    for _ in range(Q):
        X = int(input())
        results.append(cumsum[X])
    
    print('\n'.join(map(str, results)))

if __name__ == '__main__':
    main()

この解説は claude4.5opus によって生成されました。