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