Overview

In a rooted tree, we process multiple queries that add a value to the entire subtree of a specified vertex, and determine the final value of each vertex. This can be solved efficiently by combining an Euler tour with a difference array (imos method).

Analysis

Naive Approach and Its Issues

If we naively add \(D_j\) to every vertex in the subtree rooted at plant \(X_j\) for each query, we may need to update \(O(N)\) vertices per query in the worst case. With \(Q\) queries, the total complexity becomes \(O(NQ)\), which for \(N, Q\) both up to \(2 \times 10^5\) results in \(4 \times 10^{10}\) operations, causing TLE (Time Limit Exceeded).

Key Insight: Subtrees Correspond to Contiguous Intervals

When we compute an Euler tour (DFS-order visitation timestamps) on a rooted tree, the vertices belonging to the subtree of any vertex \(v\) correspond to a contiguous interval \([\text{in}[v], \text{out}[v]]\) on the Euler tour.

This allows us to transform “add a value to the entire subtree” into “add a value to a contiguous interval of an array.” Addition over a contiguous interval can be processed in \(O(1)\) using a difference array (imos method).

Concrete Example

Consider the following tree (\(N = 5\), root is \(1\)):

    1
   / \
  2   3
 / \
4   5

Assigning numbers in Euler tour visitation order:

Vertex	in_time	out_time
1	0	4
2	1	3
3	4	4
4	2	2
5	3	3

The subtree of vertex \(2\) is \(\{2, 4, 5\}\), which corresponds to the interval \([1, 3]\) on the Euler tour. Adding \(D\) to this interval achieves the addition to the entire subtree.

Algorithm

1. Tree Construction: Read the parent-child relationships from input and build an adjacency list (list of children).

2. Euler Tour: Perform DFS from the root (vertex \(1\)) and record the entry time \(\text{in}[v]\) and exit time \(\text{out}[v]\) for each vertex. The subtree of vertex \(v\) corresponds to the interval \([\text{in}[v], \text{out}[v]]\) on the Euler tour.

3. Interval Addition via Difference Array: Prepare a difference array \(\text{diff}\) of size \(N\). For each query \((X_j, D_j)\):

   • Add \(D_j\) to \(\text{diff}[\text{in}[X_j]]\)
   • Subtract \(D_j\) from \(\text{diff}[\text{out}[X_j] + 1]\) (if within bounds)

4. Prefix Sum Computation: Take the prefix sum of the difference array to obtain the final water amount at each position on the Euler tour.

5. Result Recovery: The water amount for each vertex \(v\) is the value at index \(\text{in}[v]\) in the prefix sum array.

Complexity

• Time Complexity: \(O(N + Q)\)
  • Euler tour: \(O(N)\)
  • Processing each query: \(O(1)\) × \(Q\) times = \(O(Q)\)
  • Prefix sum and result recovery: \(O(N)\)
• Space Complexity: \(O(N)\)

Implementation Notes

• Avoiding Recursive DFS: Since \(N\) can be up to \(2 \times 10^5\), Python’s recursion limit may be exceeded. The Euler tour is implemented using iterative DFS with an explicit stack.

• Boundary Handling for the Difference Array: If \(\text{out}[X_j] + 1\) is out of bounds (\(\geq N\)), the subtraction must be skipped. This occurs when the subtree extends to the end of the array.

• Fast Input: By reading all input at once with sys.stdin.buffer.read(), we ensure that I/O does not become a bottleneck even in Python.

  Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    
    for i in range(2, N + 1):
        p = int(input_data[idx]); idx += 1
        parent[i] = p
        children[p].append(i)
    
    # Euler tour to get in/out times
    in_time = [0] * (N + 1)
    out_time = [0] * (N + 1)
    
    # Iterative DFS for Euler tour
    timer = 0
    stack = [(1, False)]
    while stack:
        node, visited = stack.pop()
        if visited:
            out_time[node] = timer - 1
        else:
            in_time[node] = timer
            timer += 1
            stack.append((node, True))
            for c in reversed(children[node]):
                stack.append((c, False))
    
    # Use difference array on Euler tour order
    # For subtree of X: add D to all positions in [in_time[X], out_time[X]]
    diff = [0] * (N + 2)
    
    for _ in range(Q):
        X = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        l = in_time[X]
        r = out_time[X]
        diff[l] += D
        if r + 1 <= N - 1:
            diff[r + 1] -= D
    
    # Prefix sum
    result = [0] * N
    current = 0
    for i in range(N):
        current += diff[i]
        result[i] = current
    
    # Map back: node with in_time[node] = i gets result[i]
    ans = [0] * (N + 1)
    for node in range(1, N + 1):
        ans[node] = result[in_time[node]]
    
    sys.stdout.write(' '.join(map(str, ans[1:])) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.