1076E. E. Vasya and a Tree

CF1076E. Vasya and a Tree

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

Vasya 有一棵包含 $n$ 个结点的树，根结点为 $1$。初始时，每个结点上的值都是 $0$。

设 $d(i, j)$ 表示结点 $i$ 和结点 $j$ 之间的距离，即从 $i$ 到 $j$ 的最短路径上的边数。我们定义结点 $x$ 的 $k$-子树为满足以下两个条件的所有结点 $y$ 的集合：

• $x$ 是 $y$ 的祖先（每个结点都是自己的祖先）；
• $d(x, y) \le k$。

Vasya 需要你处理 $m$ 个操作。第 $i$ 个操作为三元组 $v_i$、$d_i$ 和 $x_i$。对于每个操作，Vasya 会将 $x_i$ 加到 $v_i$ 的 $d_i$-子树中的每个结点上。

请你在所有操作结束后，输出树上每个结点的最终值。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$），表示树的结点数。

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

接下来一行包含一个整数 $m$（$1 \le m \le 3 \times 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$ 个操作。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示所有操作结束后第 $i$ 个结点上的值。

样例输入 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

提示

在第一个样例中，初始时各结点的值为 $0, 0, 0, 0, 0$。第一次操作后，结点的值变为 $1, 1, 1, 0, 0$。第二次操作后，结点的值变为 $1, 11, 1, 0, 0$。第三次操作后，结点的值变为 $1, 11, 1, 100, 0$。