算法思路
总体框架
我们研究的目标是：在所有满足 $\deg_T(1)=k$ 的生成树中，使按从小到大排序的边权向量 $\mathbf{w}(T)=(w_{[1]}(T)\le\cdots\le w_{[n-1]}(T))$ 在“最大边优先”的词典序下最小（先最小化 $w_{[n-1]}$，若相同再最小化 $w_{[n-2]}$，依此类推）。
算法采取两阶段思路： - 基树阶段（仅用非 $1$-边 + 每块最小的 $1$-边）： 先在 $V\setminus\{1\}$ 上用 $E_0:=E\setminus E_1$ 构造最小生成森林 $F_0^{\min}$；对每个连通块 $C$ 选取与 1 相连的最小边 $b_{\min}(C)$ 将其挂到 1 上，得到基树 $T_r^{\min}$（此时 $\deg(1)=r$）。 若 $k=r$ 则返回。 - 增添阶段（由一类边到二类边）： 当 $k>r$ 时，从剩余的 $1$-边中按“先能改进路径最大边者，再其余”的策略加入；每加入一条 $1$-边，都在新形成的环上删除路径上的最大边，直到 $\deg(1)=k$。
第二阶段的关键是对剩余 $1$-边进行类型划分与顺序选择，保证词典序意义下的全局最优。
\section{基树 $T_r^{\min}$ 的构造} - 在 $V\setminus\{1\}$ 上对 $E_0$ 按权值升序运行 Kruskal，得到最小生成森林 $F_0^{\min}$；其连通块记为 $C_1,\dots,C_r$。 - 对每个块 $ C_i $ 定义 $ b_{\min}(C_i)=\arg\min{\,w(1,v)\mid v\in C_i,\ (1,v)\in E\,} $ （若不存在，则问题不可行）。 - 令 $ T\gets F_0^{\min}\cup{\,b_{\min}(C_i)\mid i=1,\dots,r\,} $ 即得 $T_r^{\min}$，此时 $\deg_T(1)=r$。若 $k=r$，输出 $T$。
直观上，$F_0^{\min}$ 保证非 $1$-边部分的总体尽量小；而每块与 1 相连的最小边保证了跨割的最小性。后续会在正确性部分证明：这一步是任何可行解的必要选择（在词典序意义下）。
“一类/二类” $1$-边与增添顺序
设当前生成树为 $T$。对任意尚未被选用的 $1$-边 $e=(1,x)$，记
$$
M_T(1,x):=\max{\,w(f)\mid f\in P_T(1,x)\,},
$$
其中 $P_T(1,x)$ 为 $T$ 中从 1 到 $x$ 的唯一路径。 将 $e$ 加入 $T$ 会形成唯一环，按最小生成树的环性质（最小情形）应删除环上最大边，也即删除 $ M_T(1,x) $ 所对应的那条边。
据此把 $e$ 划分为： - 一类边（可改进）：若 $w(e) < M_T(1,x)$。加入 $e$ 并删除 $M_T(1,x)$ 会把更靠前的位置（较大的边）变小，从而在“最大边优先”的词典序下严格变优。 - 二类边（会变差）：若 $w(e) > M_T(1,x)$。加入 $e$ 会把某个位置的值变大，词典序严格变差；只有在无一类边可用且必须提升度数时才考虑。
增添阶段的策略
当 $\deg_T(1)<k$ 时，反复执行： - 若存在一类边：选取使 $M_T(1,x)$最大的一类边加入（从而优先降低更靠前的最大边），并删除路径上的最大边； - 否则：从二类边中选取 $w(e)$最小者加入，以最小化词典序的损失，同样删除路径上的最大边；
直至 $\deg_T(1)=k$。这一顺序选择是后续正确性证明中的核心（“先一类后二类；一类内按被替换路径最大值降序；二类内按自身权值升序”）。
离线获得一类边的排序键：Kruskal + 并查集“指派”
若直接在树上多次查询 $M_T(1,x)$ 并更新，代价较高。可以在构造 $F_0^{\min}$ 的 Kruskal 过程中，顺带为一类边生成稳定的排序键，从而整体 $O(m\log m)$。
块内最小 $1$-边记录
在并查集（DSU）中维护每个连通块 $\mathcal{B}$ 的
$$
m(\mathcal{B})=\min{\,w(1,v)\mid v\in \mathcal{B},\ (1,v)\in E\,},
$$
若不存在与 1 相连的边则记为 $+\infty$。
指派规则
当 Kruskal（升序）用某条 $E_0$-边 $e_0$ 合并两个块 $A,B$ 时，设 $a:=m(A)$, $b:=m(B)$，并令 $ a\ge b $ （交换 $A,B$ 可使之成立）。 在随后必须把两个块都“挂到 1”以满足连通性/度数的过程中， 较大的那条最小 $1$-边（即权值为 $a$ 的那条）被选入时，会在对应的环上删除 $e_0$。 因此把 $e_0$ 指派给权值为 $a$ 的那条 $1$-边：记作 $ \mathrm{kill}(a)=e_0 $ ，并把 $ w(\mathrm{kill}(a)) $ 视为该 $1$-边成为“一类边”时的排序键（即其将要“替换”的路径最大值）。
由指派得到顺序
对所有候选 $1$-边 $e=(1,x)$，若 $\mathrm{kill}(e)$ 存在且 $w(e)<w(\mathrm{kill}(e))$，则 $e$ 为一类边，且应按 $w(\mathrm{kill}(e))$从大到小排序；否则 $e$ 归入二类边，按 $w(e)$从小到大排序。 这样无需在线维护路径最大值，即可一次性得到第二阶段的选择顺序。
可行性与边界
必要条件：每个连通块至少有一条连到 1 的边，且 $r\le k\le \deg_G(1)$。增添阶段每次“加一条 $1$ 边、删环上最大边”，确保连通且最终度恰好为 $k$。
伪代码
\begin{algorithmic}[1] \State 输入：连通无向图 $G=(V,E)$，权 $w$，顶点 $1$，目标度数 $k$ \State 输出：满足 $\deg_T(1)=k$ 的词典序最小生成树 $T$
\State // 读取并拆分边：记录到 1 的最小边 \State 初始化 $\text{val}[v]\gets +\infty,\ \text{id}[v]\gets 0$ 对所有 $v$ \State $E_0\gets\varnothing$ \Comment{非 1 边} \For{每条边 $e=(x,y,w_e,\text{id}_e)\in E$} \If{$x=1$} \State $\text{val}[y]\gets\min(\text{val}[y],w_e)$,\ $\text{id}[y]\gets\text{id}_e$ \ElsIf{$y=1$} \State $\text{val}[x]\gets\min(\text{val}[x],w_e)$,\ $\text{id}[x]\gets\text{id}_e$ \Else \State $E_0\gets E_0\cup\{e\}$ \EndIf \EndFor
\State // 第一次 Kruskal（升序）：仅为计算 kill 值（记为 $\text{mx}[\cdot]$） \State 将 $E_0$ 按权值 $\uparrow$ 排序；初始化 DSU：$\mathrm{fa}[v]\gets v$ \State $\text{mx}[v]\gets -\infty$ 对所有 $v$ \For{每条 $e=(u,v,w_e)\in E_0$（升序）} \State $x\gets \mathrm{find}(u),\ y\gets \mathrm{find}(v)$ \If{$x\neq y$} \If{$\text{val}[x] > \text{val}[y]$} \State 交换 $x,y$ \Comment{保证 $\text{val}[x]\le \text{val}[y]$} \EndIf \State $\mathrm{fa}[y]\gets x$ \State $\text{mx}[y]\gets w_e$ \Comment{把合并边指派给“较大的那条块内最小 1 边”} \EndIf \EndFor
\State // 组装 1 边候选序列 $tr$：前缀为各块的基边 $b_{\min}$ \State 压缩并查集；令 $p\gets 0$，$tr\gets [\,]$ \For{$v\in V\setminus\{1\}$} \If{$\mathrm{find}(v)=v$} \Comment{以根代表一个块 $C$} \State 将 $(1,v,\text{val}[v],\text{id}[v])$ 追加到 $tr$ \State $\text{val}[v]\gets +\infty$；$p\gets p+1$ \EndIf \EndFor
\State // 一类 1 边：$\text{val}[v] < \text{mx}[v]$，按 $\text{mx}$ 降序 \For{$v\in V\setminus\{1\}$} \If{$\text{val}[v] < \text{mx}[v]$} \State 将 $(1,v,\text{val}[v],\text{id}[v])$ 追加到 $tr$ \State $\text{val}[v]\gets +\infty$ \EndIf \EndFor \State 将 $tr[p+1\,..\,|tr|]$ 按 $\text{mx}[v]$ 降序排序；$p\gets |tr|$
\State // 二类 1 边：余下的 $\text{val}$，按自身权值升序 \For{$v\in V\setminus\{1\}$} \If{$\text{val}[v] < +\infty$} \State 将 $(1,v,\text{val}[v],\text{id}[v])$ 追加到 $tr$ \EndIf \EndFor \State 将 $tr[p+1\,..\,|tr|]$ 按 $w$ 升序排序
\State // 选择前 $k$ 条 1 边，并并到根 1；再用 $E_0$ 升序 Kruskal 补齐到 $n-1$ \State 重新初始化 DSU：$\mathrm{fa}[v]\gets v$ \For{$i \gets 1$ to $k$} \State $\mathrm{fa}[\,tr[i].y\,]\gets 1$ \EndFor \State $T\gets \{\,tr[1],\dots,tr[k]\,\}$ \For{每条 $e=(u,v,w_e,\text{id}_e)\in E_0$（与上相同的升序）} \State $x\gets \mathrm{find}(u)$，$y\gets \mathrm{find}(v)$ \If{$x\neq y$} \State $\mathrm{fa}[x]\gets y$ \State $T\gets T\cup\{e\}$ \EndIf \EndFor
\State \Return $T$ \end{algorithmic}
小结
本章给出了算法的构造性蓝图：先以 $F_0^{\min}\!+\!\{b_{\min}\}$ 得到基树，再用“一类边优先、类内有序”的规则增添 $1$-边至恰好 $k$ 条；并通过 Kruskal+DSU 的“指派”机制离线获得一类边的排序键，使得实现层面维持在 $O(m\log m)$ 的复杂度。