修桥笑传之坚决不用第一版方案：题解¶

解法比较¶

出题人解法先用 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<w\) 的最大边权，得到该非树边所能产生的最小正增量；记录最大的两个不同路径边权就足够完成这一选择。遍历全部非树边并取最小值，即得到答案。

复杂度¶

排序与最小生成树为 \(O(m\log m)\) ，二进制提升预处理为 \(O(n\log n)\) ，所有路径查询为 \(O(m\log n)\) ；空间为 \(O(n\log n+m)\) .