CF1119F Niyaz and Small Degrees

Niyaz 有一棵包含 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。树是一种无环连通图。 树中的每条边都有一个严格为正的整数权值。一个顶点的度数是与该顶点相连的边的数量。 Niyaz 不喜欢树中有顶点的度数过大。对于每个 $x$，其中 $0 \leq x \leq n-1$，他想要找到删除一组边的最小总权值，使得所有顶点的度数都不超过 $x$。

第一行包含一个整数 $n$（$2 \leq n \leq 250\,000$），表示 Niyaz 的树的顶点数。 接下来的 $n-1$ 行，每行包含三个整数 $a$、$b$、$c$（$1 \leq a, b \leq n$，$1 \leq c \leq 10^6$），表示一条连接顶点 $a$ 和顶点 $b$ 的边，以及该边的权值 $c$。保证给定的边构成一棵树。

输出 $n$ 个整数，对于每个 $x=0,1,\ldots,n-1$，输出一组边的最小总权值，使得删除这些边后，所有顶点的度数都不超过 $x$。

在第一个样例中，顶点 $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$。 由 ChatGPT 4.1 翻译