Overview

This problem asks you to find the sum (cumulative sum) of the values of all vertices on the path from a specified vertex to the root (vertex 1) in a rooted tree structure.

Analysis

For each query specifying a person \(X\), if we naively traverse parents one by one to compute the total, in the worst case (e.g., when the family tree forms a straight line), a single query takes \(O(N)\) time. Since there are \(Q\) queries, the total time complexity becomes \(O(NQ)\), which will not meet the time limit under the given constraints (\(N, Q \leq 2 \times 10^5\)).

Therefore, we utilize the property that “the cumulative inheritance of a person can be easily computed if the cumulative inheritance of their parent is known.” Specifically, let \(S_i\) be the cumulative inheritance of person \(i\), \(V_i\) be their own inheritance, and \(P_i\) be their parent. The following relation holds: $\(S_i = V_i + S_{P_i}\)$

A critically important constraint of this problem is that “the parent \(P_i\) of person \(i\) always has a smaller index than \(i\) (\(P_i < i\)).” Thanks to this, if we compute \(S_i\) in order from person \(1\), when we compute the cumulative inheritance of person \(i\), the cumulative inheritance of their parent \(S_{P_i}\) is guaranteed to have already been computed.

Algorithm

1. Prepare an array \(S\) to store cumulative inheritances.
2. Set the cumulative inheritance of person 1 (the root) as \(S_1 = V_1\).
3. For \(i = 2, 3, \ldots, N\) in order, perform the following computation:
   • \(S_i = V_i + S_{P_i}\)
4. For each query \(X_j\), answer with the precomputed value \(S_{X_j}\).

By precomputing the answers for all vertices in advance, each query can be answered in \(O(1)\).

Complexity

• Time complexity: \(O(N + Q)\)
  • The precomputation takes \(O(N)\), and processing the queries takes \(O(Q)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array storing cumulative inheritances and the lists holding input data.

Implementation Notes

• Fast I/O: Since \(N\) and \(Q\) are large, repeatedly calling Python’s standard input() may be slow. We achieve speedup by reading all input at once with sys.stdin.read().split() and writing all output at once with sys.stdout.write().

• Order of computation: By leveraging the constraint \(P_i < i\), we can simply loop from \(2\) to \(N\) and fill in the values in the correct order, similar to dynamic programming (DP).

• 1-indexed handling: Since person numbers start from 1, setting the array size to \(N+1\) and aligning the indices helps prevent implementation mistakes.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.