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.

输入输出样例

输入样例 #1

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

输出样例 #1

1 11 1 100 0 

输入样例 #2

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

输出样例 #2

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