有度数限制的最小生成树

以下所有令有度数限制的点为 $s$，常数为 $k$。

考虑把 $s$ 从做法中独立出来，即建立一个以 $s$ 为根的生成树。

如果某一个非 $s$ 的点与 $s$ 间有直接连边，则它可以构成 $s$ 的一度，规定点权就是这条边的边权，如果没有直接连边点权为正无穷。
显然最后只能选 $k$ 个点权非正无穷的点当做 $s$ 的直接孩子。

先对非 $k$ 点求最小生成树（森林），组成答案的边也一定在最小生成树（森林）上，显然每一棵生成树中一定有一个点权非正无穷的，我们令点权最小的点为树根。
如果此时森林中树的个数大于 $k$，则一定不可能存在答案。
因为此时我们需要增加树的个数，所以一定要破坏原有最小生成树（森林）。

考虑加点的代价，即为 $+E_u-w(u,v)$，注意能加树的当且仅当 $E_u$ 不为正无穷。

所以排序做一下即可。

与例 1 基本相同。

这里不必须加点，但是 $+E_u-w(u,v)$ 不一定为正，所以还需要加点求最小。

如果有多个点有度数限制，能不能有可靠解法？如果生成树是 $k$ 叉树，有没有非 NP-Hard 解法？

希望读者能够思考出这些问题，并拿到图灵奖！