Overview

Given a plant network represented as a tree structure, we perform multiple watering operations (adding water to an entire subtree) and determine the final water amount for each plant.

Analysis

Each watering operation adds \(D_j\) to all plants contained in the subtree rooted at the specified plant \(X_j\). A naive implementation would traverse the entire subtree for each query, resulting in \(O(NQ)\) time in the worst case. Since \(N\) and \(Q\) can be up to \(2 \times 10^5\), this approach cannot run within the time limit.

Therefore, we need to consider an efficient method. The key observation is that the final water amount of each node (plant) is the sum of \(D_j\) values from all watering operations performed on that node itself and all of its ancestor nodes. This is because a watering operation on a node \(v\) affects all descendant nodes of \(v\).

Algorithm

1. Tree Construction: Represent the tree as an adjacency list from the input. Plant 1 is the root.
2. Query Processing: For each watering query \((X_j, D_j)\), directly add \(D_j\) to node \(X_j\). This records the value of operations performed on node \(X_j\).
3. Cumulative Sum Propagation: Perform BFS (Breadth-First Search) from the root (plant 1), adding each node \(u\)’s value to its direct child nodes \(v\). As a result, each node \(v\)’s value becomes the total sum of operations performed on itself and its ancestors (i.e., the final water amount).

This approach is efficient because it first batches all queries together, then only requires a single traversal of the tree.

Complexity

• Time complexity: \(O(N + Q)\)
  • Tree construction: \(O(N)\)
  • Query processing: \(O(Q)\)
  • BFS: \(O(N)\)
• Space complexity: \(O(N)\)
  • Memory required for graph representation and answer array

Implementation Notes

• Input reading uses sys.stdin.read().split() and processes it with an iterator for speed optimization.

• The graph uses 1-indexed rather than 0-indexed numbering.

• Using DFS (Depth-First Search) instead of BFS would yield the same result, but BFS is chosen because deep tree shapes could hit recursion limits with DFS.

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it)); q = int(next(it))
    
    graph = [[] for _ in range(n+1)]
    for i in range(2, n+1):
        p = int(next(it))
        graph[p].append(i)
    
    ans = [0] * (n+1)
    for _ in range(q):
        x = int(next(it)); d = int(next(it))
        ans[x] += d
    
    queue = deque([1])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            ans[v] += ans[u]
            queue.append(v)
    
    print(' '.join(map(str, ans[1:])))

if __name__ == '__main__':
    main()

This editorial was generated by deepseekv3.