Vasya and a Tree

题意： Vasya有一棵树，它有n个节点，1号节点为根节点，初始所有点的权值为0。 定义以下两个东西： 1 函数d(i,j) 指节点i到j所经过边的数量。 2 x节点的k级子树 指满足以下条件点的集合： ① x为该点的祖先，规定自己也是自己的祖先。 ②$d(i,j) \leq k$。 Vasya有m条要求要你来解决： 给出v,d,x，将以v节点的d级子树的权值加上x。 当处理完Vasya所有的要求时，输出所有点的权值。 输入数据： 第1行包括一个整数，n（$1 \leq n \leq 3 \cdot 10^{5}$），含义如上。 第2行到第n行，包括两个整数x和y（$1 \leq x,y \leq n$），用空格隔开，表示两个点之间有一条边。 第n+1行有一个整数m（$1 \leq m \leq 3 \cdot 10^{5}$），表示有m个要求。 第n+2行到第n+m+1行，有三个整数v,d,x（$ 1 \leq v_{i} \leq n , 0 \leq d_{i} \leq 10^{9} , 1 \leq x_{i} \leq 10^{9}$），用空格隔开，含义如上。 输出数据： 共1行，包括n个数字，用空格隔开，第i个数字表示i号节点的权值。 样例1解释： 在第一次修改后，修改了1,2,3号节点，他们的权值加1，所有的权值为1,1,1,0,0。 在第二次修改后，修改了2号节点，他的权值加10，所有的权值为1,11,1,0,0。 在第三次修改后，修改了4号节点，他的权值加100，所有的权值为1,11,1,100,0。

Vasya has a tree consisting of $ n $ vertices with root in vertex $ 1 $ . At first all vertices has $ 0 $ written on it. Let $ d(i, j) $ be the distance between vertices $ i $ and $ j $ , i.e. number of edges in the shortest path from $ i $ to $ j $ . Also, let's denote $ k $ -subtree of vertex $ x $ — set of vertices $ y $ such that next two conditions are met: - $ x $ is the ancestor of $ y $ (each vertex is the ancestor of itself); - $ d(x, y) \le k $ . Vasya needs you to process $ m $ queries. The $ i $ -th query is a triple $ v_i $ , $ d_i $ and $ x_i $ . For each query Vasya adds value $ x_i $ to each vertex from $ d_i $ -subtree of $ v_i $ . Report to Vasya all values, written on vertices of the tree after processing all queries.

The first line contains single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — number of vertices in the tree. Each of next $ n - 1 $ lines contains two integers $ x $ and $ y $ ( $ 1 \le x, y \le n $ ) — edge between vertices $ x $ and $ y $ . It is guarantied that given graph is a tree. Next line contains single integer $ m $ ( $ 1 \le m \le 3 \cdot 10^5 $ ) — number of queries. Each of next $ m $ lines contains three integers $ v_i $ , $ d_i $ , $ x_i $ ( $ 1 \le v_i \le n $ , $ 0 \le d_i \le 10^9 $ , $ 1 \le x_i \le 10^9 $ ) — description of the $ i $ -th query.

Print $ n $ integers. The $ i $ -th integers is the value, written in the $ i $ -th vertex after processing all queries.

5
1 2
1 3
2 4
2 5
3
1 1 1
2 0 10
4 10 100

1 11 1 100 0 

5
2 3
2 1
5 4
3 4
5
2 0 4
3 10 1
1 2 3
2 3 10
1 1 7

10 24 14 11 11 

In the first exapmle initial values in vertices are $ 0, 0, 0, 0, 0 $ . After the first query values will be equal to $ 1, 1, 1, 0, 0 $ . After the second query values will be equal to $ 1, 11, 1, 0, 0 $ . After the third query values will be equal to $ 1, 11, 1, 100, 0 $ .