分数: 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