CF1076E Vasya and a Tree

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$ 个结点上的值。

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