ABC138 D - Ki

問題原文

atcoder.jp

問題要旨

頂点１を根とする、 頂点の木が与えられる。各頂点にはカウンターが設置されており、最初その値は０である。
また以下のような操作が 回行われる。

• 頂点 を根とする部分木の頂点全てのカウンターの値を 増やす。

全ての操作終了後の、各頂点のカウンターの値がそれぞれいくらか求めよ。

解法

毎回部分木の頂点全てを探索するのは間に合わない。逆にいえば、なんらかの方法でまとめて操作を扱う必要がある。
これは、とりあえず各 の値だけ増やしておいて、 頂点１からカウンターの値を拾いながら子に向かって降りていけばいい。

実装

N, Q = map(int, input().split())
T = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


ans = [None] * N
V = [0] * N
for q in range(Q):
    p, x = map(int, input().split())
    p -= 1
    V[p] += x


stack = [[0, V[0]]]
while stack:
    n, v = stack.pop()
    ans[n] = v

    for to in T[n]:
        if ans[to] is not None:
            continue

        stack.append([to, v + V[to]])


print(*ans, sep=' ')

感想

解説によれば、こういう問題は「1-2-3-4」みたいな直線の木を考えると助けになることが多いらしい。
覚えておこう。