概要

根が人物 \(1\) の木に対して、「人物 \(X\) から根までの経路上の \(V\) の総和」を各クエリごとに答える問題です。各人物の「根までの累積和」を前計算しておけば、クエリは即答できます。

考察

累積遺産とは、人物 \(X\) 自身を含めて \(X \to \cdots \to 1\) と親をたどっていったときに出会う全員の遺産 \(V\) の合計です。

素朴な方法が遅い理由

各クエリごとに - \(X\) から親 \(P_X\)、さらにその親…と根までたどって足し算する

とすると、最悪の場合（木が一直線の鎖）では 1 クエリに \(O(N)\) かかります。
すると全体で \(O(NQ)\) となり、\(N,Q \le 2\times 10^5\) では間に合いません。

重要な気づき（DPの形）

人物 \(i\) の累積遺産を \(cum[i]\) とすると、

• 根：\(cum[1] = V_1\)
• それ以外：\(cum[i] = cum[P_i] + V_i\)

が成り立ちます。つまり「親までの累積に自分の分を足すだけ」です。

さらに制約に \(P_i < i\) があるため、人物を \(1,2,\dots,N\) の順に処理すれば、必ず親の \(cum\) が先に計算済みになります（木をわざわざDFSしなくてもよい）。

アルゴリズム

1. 配列 \(V\)（遺産）と \(P\)（親）を読み込む。
2. 配列 \(cum\) を用意し、以下で前計算する。
   • \(cum[1] = V_1\)
   • \(i=2\) から \(N\) まで順に
     \(cum[i] = cum[P_i] + V_i\)
3. 各クエリ \(X_j\) について、答えはそのまま \(cum[X_j]\) を出力する。

（例）
\(1\) の子が \(2\)、\(2\) の子が \(3\) のとき
\(cum[1]=V_1\)、\(cum[2]=V_1+V_2\)、\(cum[3]=V_1+V_2+V_3\) と一度作っておけば、どの \(X\) でも即座に答えられます。

計算量

• 時間計算量: 前計算 \(O(N)\)、クエリ処理 \(O(Q)\) なので合計 \(O(N+Q)\)
• 空間計算量: 配列 \(V,P,cum\) により \(O(N)\)

実装のポイント

• 累積和は最大で \(N \times 10^9 \approx 2\times 10^{14}\) になり得るため、言語によっては 64bit 整数が必要です（Python は任意精度なので問題なし）。

• 入力サイズが大きいので、sys.stdin.buffer.read() でまとめて読み、出力もまとめて行うと高速です。

• \(P_i < i\) を利用して、\(i=2\) から順に cum[i] = cum[P[i]] + V[i] と計算でき、木構造の探索（DFS/BFS）は不要です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    V = [0] * (N + 1)
    for i in range(1, N + 1):
        V[i] = next(it)

    P = [0] * (N + 1)
    for i in range(2, N + 1):
        P[i] = next(it)

    cum = [0] * (N + 1)
    cum[1] = V[1]
    for i in range(2, N + 1):
        cum[i] = cum[P[i]] + V[i]

    out = []
    for _ in range(Q):
        x = next(it)
        out.append(str(cum[x]))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

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