概要

木構造で表現された植物ネットワークに対して、複数の水やり操作（部分木全体に水を追加する操作）を行い、最終的な各植物の水分量を求める問題です。

考察

各水やり操作は、指定された植物 \(X_j\) を根とする部分木に含まれるすべての植物に \(D_j\) を加算する操作です。素朴に実装すると、各クエリで部分木全体を走査することになり、最悪の場合 \(O(NQ)\) 時間かかってしまいます。\(N\) と \(Q\) が最大 \(2 \times 10^5\) であるため、このアプローチでは制限時間内に実行できません。

そこで、効率的な方法を考える必要があります。重要な観察は、各ノード（植物）の最終的な水分量は、そのノード自身とそのすべての祖先ノードに対して行われた水やり操作の \(D_j\) の総和であるということです。なぜなら、あるノード \(v\) に水をやる操作は、\(v\) のすべての子孫ノードに影響するからです。

アルゴリズム

1. 木の構築: 入力から木を隣接リストで表現します。植物1が根となります。
2. クエリの処理: 各水やりクエリ \((X_j, D_j)\) に対して、ノード \(X_j\) に直接 \(D_j\) を加算します。これにより、ノード \(X_j\) に対して行われた操作の値を記録します。
3. 累積和の伝播: 根（植物1）からBFS（幅優先探索）を行い、各ノード \(u\) の値をその直接の子ノード \(v\) に加算していきます。これにより、各ノード \(v\) の値は、自身とその祖先に対して行われた操作の総和（つまり、最終的な水分量）になります。

この手法は、クエリを先にまとめて処理し、その後で木を一度走査するだけで済むため、効率的です。

計算量

• 時間計算量: \(O(N + Q)\)
  • 木の構築: \(O(N)\)
  • クエリの処理: \(O(Q)\)
  • BFS: \(O(N)\)
• 空間計算量: \(O(N)\)
  • グラフの表現と答えの配列に必要なメモリ

実装のポイント

• 入力の読み取りには sys.stdin.read().split() を使用し、イテレータで処理することで高速化しています。

• グラフは0-indexedではなく1-indexedで扱います。

• BFSの代わりにDFS（深さ優先探索）を使用しても同じ結果が得られますが、木の形状が深い場合に再帰の制限に引っかかる可能性があるため、BFSを選択しています。

  ソースコード

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

この解説は deepseekv3 によって生成されました。