Overview

Given a tree rooted at person \(1\), the problem asks us to answer queries of the form “what is the sum of \(V\) values along the path from person \(X\) to the root?” By precomputing the “cumulative sum to the root” for each person, we can answer each query instantly.

Discussion

The cumulative inheritance is the total sum of inheritance values \(V\) of everyone encountered when tracing from person \(X\) (inclusive) through \(X \to \cdots \to 1\) following parents.

Why the naive approach is too slow

If for each query we: - Trace from \(X\) to parent \(P_X\), then to its parent… all the way to the root, summing along the way

then in the worst case (when the tree is a straight chain), a single query takes \(O(N)\).
This makes the total complexity \(O(NQ)\), which is too slow for \(N,Q \le 2\times 10^5\).

Key insight (DP formulation)

Let \(cum[i]\) denote the cumulative inheritance of person \(i\). Then:

• Root: \(cum[1] = V_1\)
• Otherwise: \(cum[i] = cum[P_i] + V_i\)

In other words, “just add your own value to the cumulative sum up to your parent.”

Furthermore, since the constraint guarantees \(P_i < i\), processing persons in order \(1,2,\dots,N\) ensures that the parent’s \(cum\) value is always computed first (no need to explicitly perform DFS on the tree).

Algorithm

1. Read the arrays \(V\) (inheritance) and \(P\) (parent).
2. Prepare an array \(cum\) and precompute as follows:
   • \(cum[1] = V_1\)
   • For \(i=2\) to \(N\) in order:
     \(cum[i] = cum[P_i] + V_i\)
3. For each query \(X_j\), simply output \(cum[X_j]\).

(Example)
When \(1\)’s child is \(2\), and \(2\)’s child is \(3\):
We compute \(cum[1]=V_1\), \(cum[2]=V_1+V_2\), \(cum[3]=V_1+V_2+V_3\) once, and then any query for \(X\) can be answered immediately.

Complexity

• Time complexity: Precomputation is \(O(N)\), query processing is \(O(Q)\), so the total is \(O(N+Q)\)
• Space complexity: \(O(N)\) for the arrays \(V,P,cum\)

Implementation Notes

• The cumulative sum can reach up to \(N \times 10^9 \approx 2\times 10^{14}\), so depending on the language, 64-bit integers are required (Python has arbitrary precision, so this is not an issue).

• Since the input size is large, reading all input at once with sys.stdin.buffer.read() and batching the output is faster.

• By leveraging \(P_i < i\), we can compute cum[i] = cum[P[i]] + V[i] sequentially from \(i=2\), eliminating the need for tree traversal (DFS/BFS).

  Source Code

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

---

This editorial was generated by gpt-5.2-high.