通过路径

题目描述

有一个由 $N$ 个顶点和 $N-1$ 条边组成的树，顶点编号为 $1, 2, \dots, N$，边编号为 $1, 2, \dots, N-1$。边 $i$ 连接顶点 $a_i$ 和顶点 $b_i$。 树的每个顶点上写着一个整数。顶点 $i$ 上写的整数记为 $c_i$。初始时，$c_i = 0$。

给定 $Q$ 个查询。第 $i$ 个查询给出整数 $t_i, e_i, x_i$，查询内容如下：

• 当 $t_i = 1$ 时：对于所有从顶点 $a_{e_i}$ 出发沿边移动、不经过顶点 $b_{e_i}$ 即可到达的顶点 $v$，将 $c_v$ 改写为 $c_v + x_i$。

• 当 $t_i = 2$ 时：对于所有从顶点 $b_{e_i}$ 出发沿边移动、不经过顶点 $a_{e_i}$ 即可到达的顶点 $v$，将 $c_v$ 改写为 $c_v + x_i$。

处理完所有查询后，输出每个顶点上写的整数。

输入格式

输入按以下格式从标准输入给出：

$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$，按此顺序每行一个。

样例

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

11
110
1110
110
100

第 $1$ 个查询中，对从顶点 $1$ 出发、不经过顶点 $2$ 即可到达的顶点 $1$ 加上 $1$。

第 $2$ 个查询中，对从顶点 $4$ 出发、不经过顶点 $5$ 即可到达的顶点 $1, 2, 3, 4$ 加上 $10$。

第 $3$ 个查询中，对从顶点 $2$ 出发、不经过顶点 $1$ 即可到达的顶点 $2, 3, 4, 5$ 加上 $100$。

第 $4$ 个查询中，对从顶点 $3$ 出发、不经过顶点 $2$ 即可到达的顶点 $3$ 加上 $1000$。

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

72
8
13
26
58
72
5

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

1657
1657
2109
1703
1474
1657
3202
1474
1247
2109
2559

数据范围

• 输入均为整数
• $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$