← 返回题目列表

AtCoder · abc187_e

E. 通过路径

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一棵树 N 顶点和 N-1 边,其中顶点编号 1, 2, \dots, N 且边缘已编号 1, 2, \dots, N-1。边缘 i 连接顶点 a_i 和 b_i.
树中的每个顶点都写有一个整数。让 c_i 是写在 Vertex 上的整数 i。最初, c_i = 0.

你将得到 Q 查询。的 i第一个查询,由整数组成 t_i, e_i,和 x_i,如下:

  • If t_i = 1:对于每个顶点 v 可从 Vertex 到达 a_{e_i} 无需访问 Vertex b_{e_i} 通过遍历边,替换 c_v 与 c_v + x_i.
  • If t_i = 2:对于每个顶点 v 可从 Vertex 到达 b_{e_i} 无需访问 Vertex a_{e_i} 通过遍历边,替换 c_v 与 c_v + x_i.

处理完所有查询后,打印写入每个顶点的整数。

约束

  • 输入中的所有值都是整数。
  • 2 \le N \le 2 \times 10^5
  • 1 \le a_i, b_i \le N
  • 给定的图是一棵树。
  • 1 \le Q \le 2 \times 10^5
  • t_i \in \{1, 2\}
  • 1 \le e_i \le N-1
  • 1 \le x_i \le 10^9

输入

输入由标准输入按以下格式给出:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
Q
t_1 e_1 x_1
\vdots
t_Q e_Q x_Q

输出

打印值 c_1, c_2, \dots, c_N 处理完所有查询后,每个查询各占一行。


示例输入 1

5
1 2
2 3
2 4
4 5
4
1 1 1
1 4 10
2 1 100
2 2 1000

示例输出 1

11
110
1110
110
100

在第一个查询中,我们添加 1 到从 Vertex 可到达的每个顶点 1 无需访问 Vertex 2,即顶点 1.
在第二个查询中,我们添加 10 到从 Vertex 可到达的每个顶点 4 无需访问 Vertex 5,即顶点 1, 2, 3, 4.
在第三个查询中,我们添加 100 到从 Vertex 可到达的每个顶点 2 无需访问 Vertex 1,即顶点 2, 3, 4, 5.
在第四个查询中,我们添加 1000 到从 Vertex 可到达的每个顶点 3 无需访问 Vertex 2,即顶点 3.


示例输入 2

7
2 1
2 3
4 2
4 5
6 1
3 7
7
2 2 1
1 3 2
2 2 4
1 6 8
1 3 16
2 4 32
2 1 64

示例输出 2

72
8
13
26
58
72
5

示例输入 3

11
2 1
1 3
3 4
5 2
1 6
1 7
5 8
3 9
3 10
11 4
10
2 6 688
1 10 856
1 8 680
1 8 182
2 2 452
2 4 183
2 6 518
1 3 612
2 6 339
2 3 206

示例输出 3

1657
1657
2109
1703
1474
1657
3202
1474
1247
2109
2559