Overview

For each query, we “add \(D\) to all vertices in the subtree of a certain vertex \(X\).” We flatten the tree into an array using an Euler tour, convert subtrees into intervals, and batch-process the range additions.

Approach

A watering operation \((X, D)\) is the operation of “uniformly adding \(D\) to all nodes in the subtree rooted at \(X\).”

• Naively, for each query we would need to traverse all vertices in \(X\)’s subtree via DFS/BFS and add \(D\) to each.
  In the worst case, a single query takes \(O(N)\), and with \(Q\) queries it becomes \(O(NQ)\), which will certainly TLE for \(N, Q \le 2 \times 10^5\).

The key observations here are the following two:

1. A subtree of a tree becomes a contiguous interval when arranged in DFS order (entry time)
   That is, if we assign each vertex \(v\) an “entry time \(tin[v]\)” (when DFS first visits it) and an “exit time \(tout[v]\)” (the last time in its subtree), then the subtree of \(v\) corresponds to the interval \([tin[v], tout[v]]\) on the array.

2. A difference array is effective for processing many “uniform range additions”
   To add \(D\) to the interval \([l, r]\) of an array \(A\), we use a difference array \(diff\):
   \(diff[l] += D,\ diff[r+1] -= D\), and then take the prefix sum from the beginning to recover \(A\).

Combining these two ideas, each query can be recorded in \(O(1)\), and at the end, the answers for all vertices can be computed in \(O(N)\).

(Simple example)
If the DFS-order array is [1,2,4,5,3] and the subtree of \(X=2\) is 2,4,5, then the interval is \([1,3]\).
Thus, “adding to the subtree” can be replaced with “adding to an interval of the array.”

Algorithm

1. Build a children list children from the input parent array (root is 1).
2. Perform DFS from root 1 and compute the following (preorder Euler tour):
   
   • tin[v]: the index in visitation order
     
   • tout[v]: the last index in the subtree
     
   • euler[t]: the vertex number at time \(t\) (to map back from array to vertex later)
3. Prepare a difference array diff (of length \(N+2\)), and for each query \((x, d)\):
   
   • \(l = tin[x],\ r = tout[x]\)
     
   • diff[l] += d
     
   • diff[r+1] -= d
4. Take the prefix sum acc for \(t = 0..N-1\) to obtain the values on the array:
   
   • acc += diff[t]
     
   • This value is the final water amount for vertex euler[t], so ans[euler[t]] = acc
5. Output ans[1..N].

Complexity

• Time complexity: \(O(N + Q)\) (\(O(N)\) for DFS, \(O(Q)\) for query processing, \(O(N)\) for prefix sum)
• Space complexity: \(O(N)\) (children list, Euler tour array, difference array, etc.)

Implementation Notes

• Avoid recursive DFS: Since \(N = 2 \times 10^5\), recursion can easily become too deep in Python. The code computes tin/tout using an iterative DFS with an explicit stack.

• tout[u] is the “last time in the subtree,” so it is set to time - 1 at the point when all children of \(u\) have been fully processed (the tout[u] = time - 1 in the code).

• Since the difference array accesses diff[r+1], the size is set to N+2 to safely handle boundary cases.

  Source Code

import sys

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

    children = [[] for _ in range(N + 1)]
    for v in range(2, N + 1):
        p = next(it)
        children[p].append(v)

    tin = [0] * (N + 1)
    tout = [0] * (N + 1)
    euler = [0] * N

    time = 0
    tin[1] = 0
    euler[0] = 1
    time = 1
    stack = [(1, 0)]
    while stack:
        u, i = stack[-1]
        if i < len(children[u]):
            v = children[u][i]
            stack[-1] = (u, i + 1)
            tin[v] = time
            euler[time] = v
            time += 1
            stack.append((v, 0))
        else:
            tout[u] = time - 1
            stack.pop()

    diff = [0] * (N + 2)
    for _ in range(Q):
        x = next(it)
        d = next(it)
        l = tin[x]
        r = tout[x]
        diff[l] += d
        diff[r + 1] -= d

    ans = [0] * (N + 1)
    acc = 0
    for t in range(N):
        acc += diff[t]
        ans[euler[t]] = acc

    sys.stdout.write(" ".join(map(str, ans[1:])))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.