题目描述

有一棵包含 N 个顶点和 N-1 条边的树，顶点编号为 1,2,…,N，边编号为 1,2,…,N-1。第 i 条边连接顶点 a[i] 和顶点 b[i]。树上的每个顶点 i 上写有一个整数 c[i]，初始时 c[i]=0。 接下来有 Q 个查询。第 i 个查询给出整数 ti,ei,xi，其含义如下： 1)当 ti=1 时：对于所有可以从顶点 a[ei]出发，且不经过顶点 b[ei]到达的顶点 v，将 c[v] 替换为 c[v]+xi。 2)当 ti=2 时：对于所有可以从顶点 b[ei]出发，且不经过顶点 a[ei]到达的顶点 v，将 c[v] 替换为 c[v]+xi。 请在所有查询处理完毕后，输出每个顶点上的整数。

输入格式

输入按以下格式从标准输入读入。 N a[1] b[1] a[2] b[2] ... a[N-1] b[N-1] Q t[1] e[1] x[1] t[2] e[2] x[2] ... t[Q] e[Q] x[Q]

输出格式

请按顺序输出所有顶点 c1,c2,…,cN的值，每行输出一个。

样例

输入样例 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

输入样例 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

提示

数据规模：所有输入均为整数。2≤N≤2×10^5; 1≤a[i],b[i] ≤N; 给定的图保证是一棵树。 1≤Q≤2×10^5; ti∈{1,2}; 1≤ei ≤N-1; 1≤xi ≤10^9。

思路分析：两种操作类型： 1 i w：以a[i]为起点遍历所有的点且路径上不能经过b[i]，路径上的所有点加w 2 i w：以b[i]为起点遍历所有的点且路径上不能经过a[i]，路径上的所有点加w 两种操作实质是一样的，就是起点不同。 如果起点为u ，不能经过的点为v： 如果dep[u] < dep[v] 就是把除了v的子树外的所有点加w； 如果dep[u] > dep[v] 就是只把u的子树加w； 运用树上差分，但是本题的差分需要从上往下（根往叶）。 假设根节点为1， 1、先预处理出每个节点的深度 2、每个操作进行一次差分处理： 如果dep[u] < dep[v]，我们把整棵树都加w，即c[1]+=w，然后把v子树c[v]减去w抵消增加的w（v子树不变）。 如果dep[u] > dep[v]，把u的子树加w，即c[u]+=w。 3、对树做一次先序遍历，求前缀和。