AT_abc187_e.[ABC187E] Through Path

有一棵包含 $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$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
$Q$
$t_1$ $e_1$ $x_1$
$t_2$ $e_2$ $x_2$
$\vdots$
$t_Q$ $e_Q$ $x_Q$

请按顺序输出所有顶点 $c_1, c_2, \dots, c_N$ 的值，每行输出一个。

数据范围

• 所有输入均为整数。
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• 给定的图保证是一棵树。
• $1 \leq Q \leq 2 \times 10^5$
• $t_i \in \{1, 2\}$
• $1 \leq e_i \leq N-1$
• $1 \leq x_i \leq 10^9$

样例说明 1

第 $1$ 个查询，从顶点 $1$ 出发，不经过顶点 $2$，可以到达的顶点只有 $1$，因此 $1$ 加上 $1$。
第 $2$ 个查询，从顶点 $4$ 出发，不经过顶点 $5$，可以到达的顶点有 $1, 2, 3, 4$，每个都加上 $10$。
第 $3$ 个查询，从顶点 $2$ 出发，不经过顶点 $1$，可以到达的顶点有 $2, 3, 4, 5$，每个都加上 $100$。
第 $4$ 个查询，从顶点 $3$ 出发，不经过顶点 $2$，可以到达的顶点只有 $3$，因此 $3$ 加上 $1000$。

由 ChatGPT 4.1 翻译