概要

この問題は、根付き木構造において、指定された頂点から根（頂点 1）までのパス上にあるすべての頂点の値の合計（累積和）を求める問題です。

考察

各クエリで指定される人物 \(X\) について、愚直に親を一人ずつ辿って合計を計算すると、最悪の場合（家系図が一直線に並んでいる場合など）1つのクエリに \(O(N)\) の時間がかかります。クエリの数は \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となり、今回の制約（\(N, Q \leq 2 \times 10^5\)）では実行時間制限に間に合いません。

そこで、「ある人物の累積遺産は、その親の累積遺産がわかれば簡単に計算できる」という性質を利用します。 具体的には、人物 \(i\) の累積遺産を \(S_i\)、自身の遺産を \(V_i\)、親を \(P_i\) とすると、以下の関係が成り立ちます。 $\(S_i = V_i + S_{P_i}\)$

この問題の非常に重要な制約として、「人物 \(i\) の親 \(P_i\) は必ず \(i\) より小さい番号である (\(P_i < i\))」という点があります。 このおかげで、人物 \(1\) から順番に \(S_i\) を計算していけば、人物 \(i\) の累積遺産を計算する時には、その親の累積遺産 \(S_{P_i}\) は必ず計算済みであることが保証されます。

アルゴリズム

1. 累積遺産を格納する配列 \(S\) を用意します。
2. 根である人物 1 の累積遺産を \(S_1 = V_1\) とします。
3. \(i = 2, 3, \ldots, N\) の順に、以下の計算を行います。
   • \(S_i = V_i + S_{P_i}\)
4. 各クエリ \(X_j\) に対して、事前に計算しておいた \(S_{X_j}\) を回答します。

このように、あらかじめすべての頂点に対する答えを計算しておく（前計算する）ことで、各クエリには \(O(1)\) で答えることができます。

計算量

• 時間計算量: \(O(N + Q)\)
  • 前計算に \(O(N)\)、クエリの処理に \(O(Q)\) かかります。
• 空間計算量: \(O(N)\)
  • 累積遺産を保持する配列や、入力を保持するリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) と \(Q\) が大きいため、Python の標準的な input() を繰り返すと時間がかかる場合があります。sys.stdin.read().split() で一括で読み込み、sys.stdout.write() で一括で出力することで高速化を図っています。

• 計算の順番: 制約 \(P_i < i\) を利用し、ループを \(2\) から \(N\) まで回すだけで正しい順序で動的計画法（DP）のように値を埋めることができます。

• 1-indexed の扱い: 人物番号が 1 から始まるため、配列のサイズを \(N+1\) にして、インデックスを合わせると実装ミスを防ぎやすくなります。

  ソースコード

import sys

def solve():
    # 入力をすべて一度に読み込み、空白文字（スペース、改行など）で分割してリストに格納します。
    # この手法は、大量の入力を高速に処理するのに適しています。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: 一族の人数, Q: クエリの数
    N = int(data[0])
    Q = int(data[1])
    
    # S[i] は人物 i の累積遺産（人物 i から人物 1 までの遺産の合計）を格納します。
    # 1-indexed で管理するため、サイズ N+1 の配列を用意します。
    S = [0] * (N + 1)
    
    # 遺産の価値 V_1, V_2, ..., V_N はリストの 2 番目から N+1 番目に格納されています。
    # まずは各人物自身の遺産価値を S[i] に代入します。
    for i in range(1, N + 1):
        S[i] = int(data[i + 1])
        
    # 親の番号 P_2, P_3, ..., P_N はリストの N+2 番目から 2*N 番目に格納されています。
    # 人物 i の親の番号を P_i とすると、累積遺産 S[i] は「自身の遺産 V_i + 親の累積遺産 S[P_i]」となります。
    # 制約 P_i < i により、人物 i の親の累積遺産 S[P_i] は、人物 i を計算する時点ですでに計算済みであることが保証されています。
    for i in range(2, N + 1):
        # P_i は data[N + i] に位置します。
        parent = int(data[N + i])
        S[i] += S[parent]
        
    # クエリ X_1, X_2, ..., X_Q はリストの 2*N+1 番目以降に格納されています。
    # 各クエリに対して、事前に計算した S[X] を文字列として取得します。
    offset = 2 * N + 1
    results = [str(S[int(data[offset + j])]) for j in range(Q)]
        
    # すべてのクエリ結果を改行で結合し、一度に出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。