Branched Evolution

Competitive Programming in Python

ABC 187 E - Through Path

各頂点に整数が書かれた木に対して、クエリを処理していく。各クエリでは辺$(a,b)$と整数$x$が与えられ、$a$から$b$を通らずに到達できるすべての頂点に$x$を足し、最終的に各頂点に書かれた整数を答える。

E - Through Path

解説

問題文ではクエリが$2$種類あるが、$2$つめのクエリでは$a$と$b$を入れ替えるだけで$1$つめのクエリに帰着するので$1$種類だけで考える。

頂点$0$を根とする根付き木として考える。ある頂点$a$に$x$が置かれているとする。このとき根から順に累積和をとると、$a$以下の頂点すべてに$x$を遷移させることできる。

クエリで与えられる辺$(a,b)$について$a$と$b$の一方がもう一方の親なので、どちらが親かで場合を分けて考える。

$a$が親の場合、$0$に$x$を置き、$b$以下に$x$を遷移させたくないので$b$に$-x$を置く。

$b$が親の場合、$a$に$x$を置く。

最後に$0$から累積和をとれば各頂点の整数がわかる。

実装

Submission #19170614 - AtCoder Beginner Contest 187

n = int(input())
graph = [set() for _ in range(n)]
edge = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].add(b)
    graph[b].add(a)
    edge.append((a, b))
# 根付き木の構成
que = [0]
visited = [0] * n
parent = [None] * n
while que:
    a = que.pop()
    visited[a] = 1
    for b in graph[a]:
        if visited[b]:
            continue
        que.append(b)
        parent[b] = a
# 各頂点に整数を置く
c = [0] * n
for _ in range(int(input())):
    t, e, x = map(int, input().split())
    a, b = edge[e - 1]
    if t == 2:
        a, b = b, a
    if a == parent[b]:
        c[0] += x
        c[b] -= x
    else:
        c[a] += x
# 根から順に累積和をとる
que = [0]
visited = [0] * n
while que:
    a = que.pop()
    visited[a] = 1
    for b in graph[a]:
        if visited[b]:
            continue
        que.append(b)
        c[b] += c[a]
print(*c, sep="\n")