CF1076E Vasya and a Tree

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.

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