CF1076E：Vasya and a Tree（DFS&差分）

Vasya has a tree consisting of n n vertices with root in vertex 1 1 . At first all vertices has 0 0 written on it.

Let d(i,j) d(i,j) be the distance between vertices i i and j j , i.e. number of edges in the shortest path from i i to j j . Also, let‘s denote k k -subtree of vertex x x — set of vertices y y such that next two conditions are met:

• x x is the ancestor of y y (each vertex is the ancestor of itself);
• d(x,y)≤k d(x,y)≤k .

Vasya needs you to process m m queries. The i i -th query is a triple v i  vi , d i  di and x i  xi . For each query Vasya adds value x i  xi to each vertex from d i  di -subtree of v i  vi .

Report to Vasya all values, written on vertices of the tree after processing all queries.

The first line contains single integer n n (1≤n≤3⋅10 5  1≤n≤3⋅105 ) — number of vertices in the tree.

Each of next n−1 n−1 lines contains two integers x x and y y (1≤x,y≤n 1≤x,y≤n ) — edge between vertices x x and y y . It is guarantied that given graph is a tree.

Next line contains single integer m m (1≤m≤3⋅10 5  1≤m≤3⋅105 ) — number of queries.

Each of next m m lines contains three integers v i  vi , d i  di , x i  xi (1≤v i ≤n 1≤vi≤n , 0≤d i ≤10 9  0≤di≤109 , 1≤x i ≤10 9  1≤xi≤109 ) — description of the i i -th query.

Print n n integers. The i i -th integers is the value, written in the i 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 0,0,0,0,0 . After the first query values will be equal to 1,1,1,0,0 1,1,1,0,0 . After the second query values will be equal to 1,11,1,0,0 1,11,1,0,0 . After the third query values will be equal to 1,11,1,100,0 1,11,1,100,0