各頂点に整数が書かれた木に対して、クエリを処理していく。各クエリでは辺$(a,b)$と整数$x$が与えられ、$a$から$b$を通らずに到達できるすべての頂点に$x$を足し、最終的に各頂点に書かれた整数を答える。
解説
問題文ではクエリが$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")