该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在遥远的星港联盟中，N 个空间站通过 N-1 条跃迁通道连接，构成一张无环的交通网络（也就是一棵树）。联盟的后勤系统会向某些空间站群体投放能量补给，但跃迁通道具有“单向封锁”机制：投放时会指定一条通道，并声明“从某一端出发，不允许穿过通道到达另一端”。

你的任务是模拟所有投放结束后，每个空间站的累计能量值。

题目描述

给定一棵包含 N 个点、N-1 条边的树：

• 空间站编号为 1..N
• 跃迁通道（边）编号为 1..N-1
• 第 i 条通道连接空间站 u_i 与 v_i

每个空间站 i 有一个能量值 w_i，初始时 w_i = 0。

接下来有 Q 次投放操作。第 k 次操作给出三个整数 t_k, e_k, x_k：

设第 e_k 条通道连接 u = u_{e_k} 和 v = v_{e_k}。

• 若 t_k = 1：从空间站 u 出发沿通道行走，但不允许经过空间站 v。对所有能到达的空间站 p，执行 w_p += x_k。
• 若 t_k = 2：从空间站 v 出发沿通道行走，但不允许经过空间站 u。对所有能到达的空间站 p，执行 w_p += x_k。

当所有操作结束后，请输出 w_1..w_N。

输入格式

N u_1 v_1 u_2 v_2 ... u_{N-1} v_{N-1} Q t_1 e_1 x_1 t_2 e_2 x_2 ... t_Q e_Q x_Q

输出格式

输出 N 行，第 i 行输出最终的 w_i。

样例

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

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

数据范围

• 2 ≤ N ≤ 2 × 10^5
• 1 ≤ Q ≤ 2 × 10^5
• 1 ≤ u_i, v_i ≤ N
• 输入保证给出的图是一棵树
• t_k ∈ {1, 2}
• 1 ≤ e_k ≤ N-1
• 1 ≤ x_k ≤ 10^9
• 输出可能达到 2×10^14 量级，需使用 64 位整数（如 long long）

测试点编号	规模分类
1-8	N≤ 10,000， Q≤ 10,000
9-20	无约束