Score : $500$ points

问题陈述

我们有一棵有 $N$ 个顶点和 $N-1$ 条边的树，顶点编号为 $1, 2, \dots, N$，边编号为 $1, 2, \dots, N-1$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。 树中的每个顶点上都写有一个整数。设 $c_i$ 为写在顶点 $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$。

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

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

We have a tree with $N$ vertices and $N-1$ edges, where the vertices are numbered $1, 2, \dots, N$ and the edges are numbered $1, 2, \dots, N-1$. Edge $i$ connects Vertices $a_i$ and $b_i$.
Each vertex in the tree has an integer written on it. Let $c_i$ be the integer written on Vertex $i$. Initially, $c_i = 0$.

You will be given $Q$ queries. The $i$-th query, consisting of integers $t_i$, $e_i$, and $x_i$, is as follows:

• If $t_i = 1$: for each Vertex $v$ reachable from Vertex $a_{e_i}$ without visiting Vertex $b_{e_i}$ by traversing edges, replace $c_v$ with $c_v + x_i$.
• If $t_i = 2$: for each Vertex $v$ reachable from Vertex $b_{e_i}$ without visiting Vertex $a_{e_i}$ by traversing edges, replace $c_v$ with $c_v + x_i$.

After processing all queries, print the integer written on each vertex.

Constraints

• All values in input are integers.
• $2 \le N \le 2 \times 10^5$
• $1 \le a_i, b_i \le N$
• The given graph is a tree.
• $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$

Input

Input is given from Standard Input in the following format:

$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$

Output

Print the values $c_1, c_2, \dots, c_N$ after processing all queries, each in its own line.

Sample Input 1

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

Sample Output 1

11
110
1110
110
100

In the first query, we add $1$ to each vertex reachable from Vertex $1$ without visiting Vertex $2$, that is, Vertex $1$.
In the second query, we add $10$ to each vertex reachable from Vertex $4$ without visiting Vertex $5$, that is, Vertex $1, 2, 3, 4$.
In the third query, we add $100$ to each vertex reachable from Vertex $2$ without visiting Vertex $1$, that is, Vertex $2, 3, 4, 5$.
In the fourth query, we add $1000$ to each vertex reachable from Vertex $3$ without visiting Vertex $2$, that is, Vertex $3$.

Sample Input 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

Sample Output 2

72
8
13
26
58
72
5

Sample Input 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

Sample Output 3

1657
1657
2109
1703
1474
1657
3202
1474
1247
2109
2559