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.

瓦西娅有一棵由 $n$ 个顶点构成的树，根节点为顶点 $1$。初始时，所有顶点上的数值均为 $0$。

设 $d(i, j)$ 表示顶点 $i$ 与 $j$ 之间的距离，即从 $i$ 到 $j$ 的最短路径所含边的数量。此外，定义顶点 $x$ 的 $k$-子树为满足以下两个条件的所有顶点 $y$ 构成的集合：

• $x$ 是 $y$ 的祖先（每个顶点均视为自身的祖先）；
• $d(x, y) \le k$。

瓦西娅需要你处理 $m$ 个查询。第 $i$ 个查询是一个三元组 $v_i$、$d_i$ 和 $x_i$。对于每个查询，瓦西娅将值 $x_i$ 加到 $v_i$ 的 $d_i$-子树中所有顶点上。

请向瓦西娅报告：在处理完所有查询后，树中各个顶点上所写的数值。

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.

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）——树中顶点的数量。

接下来的 $n - 1$ 行每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$）——表示顶点 $x$ 与 $y$ 之间的一条边。保证给定的图是一棵树。

下一行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$）——查询的数量。

接下来的 $m$ 行每行包含三个整数 $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$）——第 $i$ 个查询的描述。

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

输出 $n$ 个整数。其中第 $i$ 个整数表示处理完所有查询后，第 $i$ 个顶点上所写的值。

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

在第一个示例中，顶点的初始值为 $0, 0, 0, 0, 0$。第一次查询后，各顶点的值变为 $1, 1, 1, 0, 0$。第二次查询后，各顶点的值变为 $1, 11, 1, 0, 0$。第三次查询后，各顶点的值变为 $1, 11, 1, 100, 0$。