Overview

This problem asks us to find the sum of inheritances along the path from each person to the root (ancestor) in a family tree structure. By precomputing the cumulative inheritance for everyone, we can answer each query in \(O(1)\).

Analysis

Naive Approach and Its Problems

For each query, we could traverse from the specified person \(X\) to the root by following parent pointers, summing up the inheritances along the path.

However, with this approach: - In the worst case, the tree depth becomes \(O(N)\) (when the tree is a straight line) - With \(Q\) queries, the total time complexity is \(O(N \times Q)\) - Since \(N, Q \leq 2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations, resulting in TLE (Time Limit Exceeded)

Key Insight

If we define the cumulative inheritance of person \(i\) as \(cumsum[i]\), the following relationship holds:

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

In other words, we can compute it by simply adding our own inheritance to our parent’s cumulative inheritance.

For example, consider the following tree:

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

• \(cumsum[1] = 100\) (the root only has its own inheritance)
• \(cumsum[2] = cumsum[1] + 50 = 150\)
• \(cumsum[3] = cumsum[2] + 30 = 180\)
• \(cumsum[4] = cumsum[2] + 20 = 170\)

Algorithm

1. Create a child list for each person as preprocessing

   • By managing edges from parent to child, we can traverse from the root in order

2. Calculate cumulative inheritances using BFS (Breadth-First Search)

   • Start from the root (person 1) and initialize \(cumsum[1] = V_1\)
   • Use a queue to process from parent to child in order
   • For each child, calculate \(cumsum[child] = cumsum[parent] + V_{child}\)

3. Query Processing

   • Simply reference the precomputed \(cumsum\) array
   • Each query can be answered in \(O(1)\)

Complexity

• Time Complexity: \(O(N + Q)\)

  • Preprocessing (BFS): Each person is processed once, so \(O(N)\)
  • Query processing: Each query is just an array lookup at \(O(1)\), and there are \(Q\) queries, so \(O(Q)\)

• Space Complexity: \(O(N)\)

  • Cumulative inheritance array \(cumsum\): \(O(N)\)
  • Child list \(children\): There are \(N-1\) edges, so \(O(N)\)
  • BFS queue: At most \(O(N)\)

Implementation Notes

1. Be careful about index offsets

   • Person numbers are from \(1\) to \(N\) (1-indexed)
   • The inheritance array \(V\) is from \(0\) to \(N-1\) (0-indexed)
   • Use V[i-1] to get person \(i\)’s inheritance

2. Handling the case when \(N = 1\)

   • Parent information doesn’t exist (person 1 has no parent)
   • Need to handle reading an empty line

3. Output optimization

   • Collect results in a list and output all at once at the end to reduce I/O overhead
   • Use '\n'.join(map(str, results)) for fast output

Source Code

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()  # Read empty line
    
    # Calculate cumulative inheritance
    # cumsum[i] = sum of inheritances from person i to root (person 1)
    cumsum = [0] * (N + 1)
    
    # Calculate from root using BFS
    # Create child list
    children = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        children[P[i]].append(i)
    
    # Calculate cumulative inheritance using BFS
    cumsum[1] = V[0]  # V[0] is person 1's inheritance
    queue = deque([1])
    
    while queue:
        node = queue.popleft()
        for child in children[node]:
            cumsum[child] = cumsum[node] + V[child - 1]  # V[child-1] is person child's inheritance
            queue.append(child)
    
    # Answer queries
    results = []
    for _ in range(Q):
        X = int(input())
        results.append(cumsum[X])
    
    print('\n'.join(map(str, results)))

if __name__ == '__main__':
    main()

This editorial was generated by claude4.5opus.