复杂度分析
参数与符号
设图 $G=(V,E)$ 中顶点数 $|V|=n$、边数 $|E|=m$，顶点 $1$ 的度为 $d_1:=\deg_G(1)=|E_1|$（$E_1$ 为与 $1$ 相邻的边集，$E_0:=E\setminus E_1$）。 在 $V\setminus\{1\}$ 上用 $E_0$ 的 Kruskal（升序）得到最小生成森林 $F_0^{\min}$，其连通块数为 $r$。 记 $\alpha(\cdot)$ 为反阿克曼函数，DSU（并查集）近似视为常数摊还。
基树阶段的代价
- 排序与 Kruskal： 对 $E_0$ 排序并运行 Kruskal，时间 $O(|E_0|\log |E_0| + |E_0|\alpha(n)) \subseteq O(m\log m)$。
- 块内最小 $1$-边： 在 Kruskal 过程中/结束后，线性扫描 $E_1$ 为每个块 $C$ 维护 $b_{\min}(C)$，时间 $O(d_1)\le O(m)$。
- 构造基树： 合并 $F_0^{\min}$ 与 $\{b_{\min}(C_i)\}_{i=1}^r$，线性时间。
综上，基树阶段时间 $O(m\log m)$，空间 $O(n+m)$。
“指派”与候选排序的代价
在 Kruskal 合并两个块 $A,B$ 的时刻，维护每块的 $m(\cdot)=$ “块内最小 $1$-边权”，并将该次合并边 $e_0$ 指派给 $\max\{m(A),m(B)\}$ 对应的 $1$-边，得到映射 $\mathrm{kill}(\cdot)$。 - 维护 $m(\cdot)$： DSU 合并时用“按秩合并+路径压缩”并携带块信息，摊还 $O(1)$。 - 指派记录： 每次合并常数时间追加一条记录，总代价 $O(|E_0|)$。 - 候选分类与排序： 将剩余候选 $1$-边划分为 $\mathcal{E}_1=\{e: w(e)<w(\mathrm{kill}(e))\}$（一类边）与 $\mathcal{E}_2$（二类边），并分别按 $w(\mathrm{kill}(e))$ 降序与 $w(e)$ 升序排序。 时间 $O(|\mathcal{E}_1|\log |\mathcal{E}_1| + |\mathcal{E}_2|\log |\mathcal{E}_2|)\subseteq O(d_1\log d_1)\subseteq O(m\log m)$。
增添阶段的代价
增添阶段最多执行 $k-r\le d_1$ 次“加入一条 $1$-边并删一条环上最大边”的操作。 - 挑选下一条边： 由于 $\mathcal{E}_1,\mathcal{E}_2$ 事先排好序，顺序扫描即可，摊还 $O(1)$。 - 删除的环上最大边： 采用离线“指派”后，$\mathrm{kill}(e)$ 指示将被删除的那条非 $1$-边（或其等价的路径最大边），可在 $O(1)$ 时间完成替换与集合更新。
因此增添阶段总时间 $O(k-r)\le O(d_1)\le O(m)$。
总时间与空间复杂度
综合上述各阶段：
$$
T(m,n)=O(m\log m)\quad\text{且}\quad S(m,n)=O(n+m).
$$
时间的主导来自一次全局排序与 Kruskal；其余操作为线性或近线性。
可选的在线维护方案（替代“指派”）
在某些应用中，需要动态从一棵受度或直径限制的生成树重构到另一棵，此类重新配置问题在建模与复杂度上存在额外挑战 \cite{bousquet2022reconfiguration}。
若不使用离线“指派”，可用 Link-Cut Tree（LCT）/树剖 + 线段树维护当前树上路径最大边， 则每次“加入一条 $1$-边并删除环上最大边”在 $O(\log n)$ 时间完成； 增添阶段复杂度变为 $O((k-r)\log n)$，总复杂度
$$
O(m\log m + (k-r)\log n)\subseteq O(m\log m + m\log n).
$$
在实际实现中，离线“指派”更简洁，常数因子更小。
与朴素/改进基线的比较
- 朴素枚举（仅作小规模）： 穷举 $\binom{d_1}{k}$ 种 $1$-边选择，每次做一遍 MST 检查，复杂度爆炸，仅在 $n\le 10$ 可行。
- 基于二分“最小瓶颈”的检查： 对最大边权做二分，每次用并查集验证可行性， 复杂度 $O\big(m\log m + (\log m)\cdot (m\alpha(n))\big)=\tilde O(m\log m)$，但常数较大， 且需要额外的可行性与度数达成性判断逻辑。
- 本文算法： 单次排序 + Kruskal + 离线“指派”，总体 $O(m\log m)$， 常数小、实现简洁，并且直接输出词典序最小解而非仅判定可行。
关于下界与可改进空间
在基于比较的模型下，对任意实权边集进行完全排序需要 $\Omega(m\log m)$ 次比较； Kruskal 亦以排序为主要瓶颈，因而 $O(m\log m)$ 是自然的上界。 若权值可做线性时间桶化/基数排序（例如整数小范围权），则整体可达 $O(m+n)$ 级别； 若采用更高阶的 MST 线性/次线性算法（例如随机化 Karger–Klein–Tarjan 框架）， 本问题亦可在相近的复杂度范围内实现，不过实现复杂度显著提高，且需要将单点度约束与词典序判定谨慎嵌入该框架。