1076E. E. Vasya and a Tree

\r\n

CF1076E. Vasya and a Tree

\n

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

\r\n

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

\r\n

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

\r\n

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

\r\n

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

\r\n

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

\r\n

输入格式

\r\n

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

\r\n

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

\r\n

接下来一行包含一个整数 $m$（$1 \\le m \\le 3 \\times 10^5$），表示操作数。

\r\n

接下来的 $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$ 个操作。

\r\n

输出格式

\r\n

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

\r\n

样例输入 1

\n

5\n1 2\n1 3\n2 4\n2 5\n3\n1 1 1\n2 0 10\n4 10 100

\n

样例输出 1

\n

1 11 1 100 0

\n

样例输入 2

\n

5\n2 3\n2 1\n5 4\n3 4\n5\n2 0 4\n3 10 1\n1 2 3\n2 3 10\n1 1 7

\n

样例输出 2

\n

10 24 14 11 11

\n

提示

\r\n

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

状态	递交者	时间	内存	语言	代码	递交时间
AC	汤音同	4770ms	75.2 MiB	C++17(O2)	1.2 KiB	2026-8-8 14:23:35
AC	admin	6699ms	57.4 MiB	C++11(O2)	1.8 KiB	2026-8-4 22:18:17

统计

递交统计

1076E. E. Vasya and a Tree

信息

还没有账户？

登录