← 返回题目列表

Codeforces · 1119/F

F. 尼亚兹和小度

中文机器翻译题面 查看原题

Niyaz 有一棵树,其顶点为 $$$n$$$,编号从 $$$1$$$ 到 $$$n$$$。树是没有环的连通图。

该树中的每条边都具有严格的正整数权重。顶点的度数是与该顶点相邻的边的数量。

Niyaz 不喜欢树中的顶点度数太大。对于从$$$0$$$到$$$(n-1)$$$的每一个$$$x$$$,他想要找到要删除的一组边的最小总权重,使得所有顶点的度数最多变为$$$x$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 250\,000$$$) — Niyaz 树中的顶点数。

接下来的 $$$(n - 1)$$$ 行包含三个整数 $$$a$$$、$$$b$$$、$$$c$$$ ($$$1 \le a, b \le n$$$, $$$1 \leq c \leq 10^6$$$) - 分别是由该边连接的顶点的索引及其权重。保证给定的边形成一棵树。

输出

打印 $$$n$$$ 整数:对于每个 $$$x = 0, 1, \ldots, (n-1)$$$ 打印这样一组边的最小总权重,即从该组中删除边后,所有顶点的度数都小于或等于 $$$x$$$。

示例

输入 #1

5
1 2 1
1 3 2
1 4 3
1 5 4

输出 #1

10 6 3 1 0

输入 #2

5
1 2 1
2 3 2
3 4 5
4 5 14

输出 #2

22 6 0 0 0

注意

在第一个示例中,顶点 $$$1$$$ 与所有其他顶点相连。因此,对于每个 $$$x$$$,您应该删除从顶点 $$$1$$$ 发出的 $$$(4-x)$$$ 最轻边,因此答案为 $$$1+2+3+4$$$、$$$1+2+3$$$、$$$1+2$​​$$、$$$1$$$ 和 $$$0$$$。

在第二个示例中,对于 $$$x=0$$$ 需要删除所有边,对于 $$$x=1$$$ 可以删除权重为 $$$1$$$ 和 $$$5$$$ 的两条边,而对于 $$$x \geq 2$$$ 则不需要删除边,所以答案是 $$$1+2+5+14$$$, $$$1+5$$$、$$$0$$$、$$$0$$$ 和 $$$0$$$。