# 修桥笑传之坚决不用第一版方案：题解 ## 解法比较 出题人解法先用 Kruskal 建最小生成树，再枚举非树边，在树上路径中删去严格小于该边的最大边权。倍增表维护路径最大值及次大不同值，以处理等权边；换边原理及两个不同值足够的证明见下文。 若找不到可删除的边，必须跳过这个候选；仅把最小生成树总权加上新边权，会留下一个环。Codex（GPT-6）的实现使用这一判断、64 位累计与显式遍历。设点、边数为 $n,m$ ，时间为 $O(m\log(m+1)+(n+m)\log(n+1))$ ，空间为 $O(m+n\log(n+1))$ . ## 思路 先用 Kruskal 算法求一棵最小生成树 $M$ ，设其权值为 $W_{\min}$ . 对每条不在 $M$ 中的边 $(u,v,w)$ ，把它加入 $M$ 会形成一个环。必须从 $M$ 中的 $u$ 到 $v$ 路径上删去一条边，所得造价为 $W_{\min}+w-x$ ，其中 $x$ 是被删边的权值。 为了让新造价严格大于 $W_{\min}$ 且尽量小，应删去路径上**小于 $w$ 的最大边权**。若路径最大边权等于 $w$ ，删去它只会得到另一棵同权最小生成树，因此要用次大的**不同**边权；如果不存在更小边权，这条非树边不能产生候选答案。 ## 路径查询 在最小生成树上做二进制提升。对每个顶点和每个 $2^j$ 级祖先，记录到该祖先的路径上最大的两个不同边权。合并两段路径时，从至多四个候选边权中保留最大的两个不同值。于是每条非树边的路径查询为 $O(\log n)$ . 枚举所有非树边，计算严格大于 $W_{\min}$ 的候选造价并取最小值。求树上父子关系时用迭代遍历，以免链状树造成递归栈溢出。 ## 正确性 设 $T$ 是任意一棵造价高于 $W_{\min}$ 的生成树，用 $W(T)$ 表示它的总边权，也就是总造价。生成树的交换引理允许把 $T\setminus M$ 与 $M\setminus T$ 中的边一一配对，使每对边都能在 $M$ 上进行一次合法交换。由于 $M$ 是最小生成树，每对交换的造价增量都非负；这些增量之和恰好是 $W(T)-W_{\min}>0$ . 因此至少存在一次正增量交换，且其增量不超过 $W(T)-W_{\min}$ . 特别地，严格次小的造价必能由 $M$ 的一次单边交换得到。 对于固定加入的非树边，Kruskal 的最优性保证其权值 $w$ 不小于路径上任一边权。删除满足 $x