[BJWC2010] 严格次小生成树

形式化题目

给定无向连通图 $G=(V,E)$ ， $|V|=n \leqslant 10^5$ ， $|E|=m \leqslant 3\times10^5$ ，边权 $w \in [0,10^9]$ ，可能有重边与自环。设最小生成树为 $T$ ，求权值满足 $s(T') > s(T)$ 的生成树 $T'$ 中最小的 $s(T')$ （严格次小生成树）。数据保证存在。

注意「严格」：若存在与 MST 同权值的生成树，它不算次小；我们要的是第一个严格更大的权值。

暴力解法

思路

按定义直算：01 序列枚举每条边的选/不选，生成完整方案后在叶子处用并查集检查——恰好 $n-1$ 条边且无环（即连通无环）就是生成树，统计所有生成树的权值，输出严格大于 MST 权值的最小者。

它忠实暴露了本题的难点：生成树个数是 $\binom{m}{n-1}$ 级别，枚举空间指数级；而且「严格」要求我们同时跟踪最小与严格第二小的权值，直接对齐了题目的定义。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-21 20:20
 * update_at: 2026-10-21 20:20
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 01 序列枚举：每层递归决定「第 dep 条边选 / 不选」，生成完整 choose[] 后，
// 在叶子处用并查集检查选中的边是否构成生成树（恰好 n-1 条且无环即连通无环），
// 统计所有生成树权值，输出「严格大于 MST 权值」的最小者。
// 与 main.cpp 的 Kruskal + 倍增换边完全不共享实现，因此适合独立验证。
// 生成树数量最多 C(28,7) 级别，只适合 n <= 8 的对拍数据。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 12;
const int maxm = 40;

int n, m;
int eu[maxm], ev[maxm], ew[maxm]; // 第 i 条边的两端点与权值
int choose[maxm];                 // choose[i]：1 表示选第 i 条边
ll best, second;                  // 最小生成树权值、严格次小生成树权值
ll mst_cnt;                       // 生成树计数（调试用，确认至少存在两棵不同权值）

int fa[maxn];                     // 叶子检查用的并查集

// 检查当前 choose[] 是否构成生成树；是则更新 best / second
void check() {
    for (int i = 1; i <= n; ++i) fa[i] = i;
    int cnt = 0;
    ll sum = 0;
    for (int i = 1; i <= m; ++i) {
        if (!choose[i]) continue;
        // 找两端点的根（数据极小，不压缩也无所谓）
        int ru = eu[i], rv = ev[i];
        while (fa[ru] != ru) ru = fa[ru];
        while (fa[rv] != rv) rv = fa[rv];
        if (ru == rv) return;     // 有环，不是树
        fa[ru] = rv;
        cnt++;
        sum += ew[i];
    }
    if (cnt != n - 1) return;     // 边数不对（不连通或自环浪费）
    mst_cnt++;
    if (sum < best) { second = best; best = sum; }
    else if (sum > best && sum < second) second = sum;  // 严格大于才参与次小
}

// 这一层在决定第 dep 条边选不选
void dfs_choose(int dep) {
    if (dep == m + 1) {           // 完整方案已生成
        check();
        return;
    }
    choose[dep] = 0;
    dfs_choose(dep + 1);
    choose[dep] = 1;
    dfs_choose(dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> eu[i] >> ev[i] >> ew[i];

    best = second = LLONG_MAX;
    mst_cnt = 0;
    dfs_choose(1);

    // second 仍为 LLONG_MAX 说明不存在严格次小生成树；本题数据保证存在
    if (second == LLONG_MAX)
        cout << -1 << endl;
    else
        cout << second << endl;
    return 0;
}

复杂度

每条边两个选择，共 $2^m$ 个叶子，每个叶子一次 $O(n)$ 的并查集检查，总 $O(2^m \cdot n)$ ，只适合 $n \leqslant 8$ 的对拍数据。

瓶颈

指数级的枚举空间。消除它的关键观察是：严格次小生成树一定可以由 MST 换一条边得到，于是搜索空间从「所有生成树」塌缩成「 $m$ 条非树边各换一次」。

正解

思路

一、为什么不能简单地在 MST 上换一条更大的边

一个自然的错误想法：随便挑一条非树边换掉一条更小的树边。问题有两层：

换哪条树边不是自由的。把非树边 $e=(u,v,w)$ 加入 $T$ 后出现唯一的环—— $e$ 加上 $T$ 上 $u$ 到 $v$ 的路径。要回到树，被删的边必须在这个环上（删环外的边会破坏连通性）。所以候选替换边只有「 $u\sim v$ 路径上的边」这一族，不是全树的边。
必须换「严格小于 $w$ 的最大边」。权值增量是 $w - w_{\text{被删}}$ 。要增量大于 $0$ 且尽量小，就要被删边权严格小于 $w$ 且尽可能大。若只找「最大边」，当最大边权恰好等于 $w$ 时增量为 $0$ ，得到的还是原权值，不严格。

二、枚举非树边 + 树上换边的正确性

为什么只枚举「加一条非树边、删一条树边」就能覆盖严格次小生成树？

设严格次小生成树为 $T'$ ， $s(T') > s(T)$ 。取 $T'$ 中一条不在 $T$ 里的边 $e'=(u,v)$ 。把 $e'$ 加入 $T$ 得到环 $C$ 。环上除 $e'$ 外都是 $T$ 的树边，且它们都在 Kruskal 处理 $e'$ 之前被选中（ $e'$ 是非树边），于是权值都 $\leqslant w(e')$ 。从 $C$ 上任取一条非 $e'$ 的树边删掉，得到的树 $T''$ 满足

s(T'') = s(T) - w_{\text{删}} + w(e') \leqslant s(T) + w(e') - w(e') = s(T) + 0

更准确地： $w_{\text{删}} \leqslant w(e')$ 给出 $s(T'') \leqslant s(T')$ 。若 $s(T'') < s(T')$ ，与 $T'$ 是次小矛盾；若 $s(T'') = s(T')$ ，用 $T''$ （与 $T$ 只差一条边）代替 $T'$ 重复论证，有限步后必然得到一棵与 MST 恰好差一条边、权值等于 $s(T')$ 的生成树。所以严格次小生成树的权值一定被某个「一次换边」方案取到，枚举所有非树边即可。

每条非树边的最优换法：记 $u\sim v$ 路径上的最大边权为 $m_1$ 、严格次大为 $m_2$ （不存在时记 $-\infty$ ）：

情形	最优替换	候选权值	说明
$w > m_1$	删最大边 $m_1$	$s(T) - m_1 + w$	增量 $w - m_1$ 最小且为正
$w = m_1$	删严格次大 $m_2$	$s(T) - m_2 + w$	删 $m_1$ 增量为 0，不严格
$w < m_1$	不可能	—	见下方论证

为什么 $w < m_1$ 不可能？ Kruskal 按边权非降序处理，处理到非树边 $e$ 时 $u,v$ 已经由更早（权值 $\leqslant w$ ）的边连通，这些边全部留在了 $T$ 里，所以 $u\sim v$ 路径的最大边权 $\leqslant w$ ，即 $m_1 \leqslant w$ 。

无解的形态（题面保证不发生，但论证要闭环）：所有非树边都满足 $w = m_1$ 且路径上没有严格次大边（全部同权），则任何换法增量都是 $0$ ，不存在严格次小生成树。实现里让答案保持哨兵即可识别。

三、为什么必须同时维护「严格次大」

倍增表的每个结点 $u$ 、每个层级 $j$ 维护「 $u$ 向上 $2^j$ 条边」这一段的 $(m_1, m_2)$ 。查询 $u\sim v$ 路径时把若干段两两合并。合并规则是关键：两段信息 $(a_1,a_2)$ 与 $(b_1,b_2)$ 合并时，最大值是四候选的最大者，而严格次大必须排除与最大等值的重复边——在 $a_1 = b_1$ 时次大是 $\max(a_2, b_2, \text{被淘汰的 } a_1)$ ，直接取「第二大候选」会把与最大等权的边误当成次大。

漏掉严格次大会出什么错：

$w = m_1$ 时若只有最大表，要么判「无法替换」而丢解，要么错误地用 $m_1$ 得增量 $0$ ，输出退化成 MST 权值（非严格次小）。
官方样例正是这个场景：非树边 $3\text{-}4$ 权 $3$ ，树上路径 $3\to1\to2\to4$ 的边权为 $2,1,3$ ，路径最大也是 $3$ 。只有退到严格次大 $m_2=2$ 才得到正确答案 $10-2+3=11$ （MST 由边 $1,2,3,4$ 组成，权值和 $10$ ）。

实现上的几个细节：

权值可为 $0$ ，「不存在」的哨兵必须用 $-1$ 之类，不能与真实权值混淆。
总权值上界 $3\times10^5 \times 10^9 = 3\times10^{14}$ ，必须用 long long。
自环进不了任何生成树，枚举非树边时跳过；重边被 Kruskal 自然处理。
叶级初始化： $\text{mx}_1[u][0]$ 是 $u$ 到父亲的边权， $\text{mx}_2[u][0]$ 为哨兵（一条边没有次大）；根的父边也是哨兵。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-21 20:00
 * update_at: 2026-10-21 20:00
 */
// main.cpp：[BJWC2010] 严格次小生成树。
// 先 Kruskal 求 MST，再枚举每条非树边 (u,v,w)：把它加入 MST 会与树上 u~v 路径成环，
// 换掉环上一条树边得到新生成树。为让增量 w-被删边 > 0 且最小，被删边应是路径上
// 「权值严格小于 w 的最大边」：
//   - w > 路径最大 m1 ：删 m1，候选 = sum - m1 + w
//   - w == m1        ：删 m1 增量为 0（不严格），退到严格次大 m2，候选 = sum - m2 + w
//   - w < m1 不可能发生（Kruskal 处理该非树边时，路径上的树边权都 <= w）
// 因此倍增 LCA 表要同时维护每段的 (最大, 严格次大) 边权，合并时严格排除等值重复边。
// 无解（所有非树边都不能严格替换）保持 INF；题面保证有解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;   // 点数上限
const int maxe = 3e5 + 5;   // 边数上限
const int MAXLOG = 17;      // 2^17 > 1e5，够覆盖深度
const ll NEG = -1;          // 边权 >= 0，「不存在」的哨兵用 -1（不能用 0，权值可为 0）

int n, m;
ll mst_sum;                 // MST 总权值，可达 3e5*1e9，必须 long long

// ---------- 原图边表（按 Kruskal 顺序排序后使用） ----------
struct Edge {
    int u, v;
    ll w;
    bool in_mst;            // 是否被选进 MST
};
vector<Edge> edges;

// ---------- 并查集（Kruskal 用） ----------
int fa[maxn];               // fa[x]：并查集父指针，根的父是自己
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

// ---------- MST 上的链式前向星 ----------
struct ListEdge { int v; ll w; int nxt; }; // 边权与原图同为 ll；nxt 不与 std 冲突
ListEdge g[maxe * 2];       // 无向边双向存，大小翻倍
int head[maxn], edge_cnt;
void add_edge(int u, int v, ll w) {
    g[edge_cnt] = {v, w, head[u]};
    head[u] = edge_cnt++;
}

// ---------- 倍增表：同时维护路径 (最大, 严格次大) 边权 ----------
int dep[maxn];                          // 深度，根为 1
int up[maxn][MAXLOG + 1];               // up[u][j]：u 的第 2^j 级祖先
ll mx1[maxn][MAXLOG + 1];               // mx1[u][j]：u 向上 2^j 条边的最大权
ll mx2[maxn][MAXLOG + 1];               // mx2[u][j]：同段的严格次大权（< mx1），不存在为 NEG

// 合并两段最值信息 (a1,a2) 和 (b1,b2)，返回合并后的 (最大, 严格次大)
// 次大必须排除与最大等值的重复边，这是「严格」二字在数据结构层的落点
void merge_info(ll a1, ll a2, ll b1, ll b2, ll &r1, ll &r2) {
    r1 = max(a1, b1);
    r2 = NEG;
    // 严格次大 = 四个候选里「小于 r1 的最大者」
    ll cand[4] = {a1, a2, b1, b2};
    for (int i = 0; i < 4; ++i)
        if (cand[i] < r1) r2 = max(r2, cand[i]);
}

// DFS 预处理深度、父边信息（MST 是树，直接递归；深度 <= 1e5，64MB 栈足够）
void dfs(int u, int f, int w_from_fa) {
    dep[u] = dep[f] + 1;
    up[u][0] = f;
    mx1[u][0] = w_from_fa;
    mx2[u][0] = NEG;                     // 一条边没有次大
    for (int i = head[u]; i != -1; i = g[i].nxt) {
        if (g[i].v != f) dfs(g[i].v, u, g[i].w);
    }
}

void build_lca() {
    dfs(1, 0, NEG);                      // 根的父边哨兵
    for (int j = 1; j <= MAXLOG; ++j) {
        for (int i = 1; i <= n; ++i) {
            int mid = up[i][j - 1];
            up[i][j] = up[mid][j - 1];
            merge_info(mx1[i][j - 1], mx2[i][j - 1],
                       mx1[mid][j - 1], mx2[mid][j - 1],
                       mx1[i][j], mx2[i][j]);
        }
    }
}

// 查询树上 u~v 路径的 (最大, 严格次大) 边权
void query_path(int u, int v, ll &r1, ll &r2) {
    r1 = r2 = NEG;
    if (dep[u] < dep[v]) swap(u, v);
    // u 跳到与 v 同层
    for (int j = MAXLOG; j >= 0; --j) {
        if (dep[u] - (1 << j) >= dep[v]) {
            merge_info(r1, r2, mx1[u][j], mx2[u][j], r1, r2);
            u = up[u][j];
        }
    }
    if (u == v) return;
    // 一起向上跳
    for (int j = MAXLOG; j >= 0; --j) {
        if (up[u][j] != up[v][j]) {
            merge_info(r1, r2, mx1[u][j], mx2[u][j], r1, r2);
            merge_info(r1, r2, mx1[v][j], mx2[v][j], r1, r2);
            u = up[u][j];
            v = up[v][j];
        }
    }
    // 最后各补一条连向 LCA 的父边
    merge_info(r1, r2, mx1[u][0], mx2[u][0], r1, r2);
    merge_info(r1, r2, mx1[v][0], mx2[v][0], r1, r2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    if (n == 1) {                      // 单点无树边，严格次小生成树不存在
        cout << -1 << endl;
        return 0;
    }
    edges.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].in_mst = false;
    }

    // ---- 1. Kruskal 求 MST ----
    sort(edges.begin(), edges.end(),
         [](const Edge &a, const Edge &b) { return a.w < b.w; });
    for (int i = 1; i <= n; ++i) fa[i] = i;
    int picked = 0;
    mst_sum = 0;
    for (int i = 0; i < m && picked < n - 1; ++i) {
        Edge &e = edges[i];             // 自环两端同根，天然被跳过
        int ru = find(e.u), rv = find(e.v);
        if (ru == rv) continue;
        fa[ru] = rv;
        mst_sum += e.w;
        e.in_mst = true;               // 下标引用，写回 vector 元素
        ++picked;
    }

    // ---- 2. 用树边建链式前向星 ----
    memset(head, -1, sizeof(head));
    edge_cnt = 0;
    for (const Edge &e : edges) {
        if (e.in_mst) {
            add_edge(e.u, e.v, e.w);
            add_edge(e.v, e.u, e.w);
        }
    }
    build_lca();

    // ---- 3. 枚举非树边，换边求最小严格增量 ----
    ll ans = LLONG_MAX;                  // 保持不变即为无解（题面保证有解）
    for (const Edge &e : edges) {
        if (e.in_mst || e.u == e.v) continue;
        ll m1, m2;
        query_path(e.u, e.v, m1, m2);
        if (e.w > m1) ans = min(ans, mst_sum - m1 + e.w);
        else if (e.w == m1 && m2 != NEG) // 换最大边增量 0，退到严格次大
            ans = min(ans, mst_sum - m2 + e.w);
    }

    if (ans == LLONG_MAX) ans = -1;      // 无解（题面保证不发生）
    cout << ans << endl;
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-21 20:10
# update_at: 2026-10-21 20:10

import sys
from collections import deque

type Info = tuple[int, int]  # (路径最大边权, 严格次大边权)，-1 表示不存在（边权可为 0）

NEG = -1  # 「不存在」哨兵：边权 >= 0，所以 -1 一定不与真实权值混淆


def merge(a: Info, b: Info) -> Info:
    """合并两段路径的最值信息，返回 (最大, 严格次大)。

    次大必须排除与最大等值的重复边——「严格」二字在数据结构层的落点。
    哨兵 -1 比任何真实权值都小，自然不会当上最大，只会被淘汰。
    """
    first = max(a[0], b[0])
    cands = (a[0], a[1], b[0], b[1])
    second = max((c for c in cands if c < first), default=NEG)
    return first, second


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    if n == 1:  # 单点无树边，严格次小生成树不存在
        print(-1)
        return

    # edges[i] = (u, v, w, 是否树边)；先读入再排序，in_mst 之后写回
    edges = [(next(data), next(data), next(data), False) for _ in range(m)]

    # ---- 1. Kruskal 求 MST ----
    parent = list(range(n + 1))  # parent[x]：并查集父指针

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # 路径压缩（隔代跳）
            x = parent[x]
        return x

    order = sorted(range(m), key=lambda i: edges[i][2])  # 按边权非降序处理
    mst_sum, picked = 0, 0
    for i in order:
        u, v, w, _ = edges[i]
        ru, rv = find(u), find(v)
        if ru == rv:  # 两端已连通（含自环），选它成环，跳过
            continue
        parent[ru] = rv
        mst_sum += w
        edges[i] = (u, v, w, True)
        picked += 1
        if picked == n - 1:  # 生成树恰好 n-1 条边，选满即停
            break

    # ---- 2. 用树边建邻接表，BFS 求深度/父边（迭代，不吃递归栈） ----
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for u, v, w, in_mst in edges:
        if in_mst:
            adj[u].append((v, w))
            adj[v].append((u, w))

    LOG = max(1, (n - 1).bit_length()) if n > 1 else 1  # 2^LOG >= 最大深度
    depth = [0] * (n + 1)
    up = [[0] * (LOG + 1) for _ in range(n + 1)]    # up[u][j]：u 的第 2^j 级祖先
    info = [[(NEG, NEG)] * (LOG + 1) for _ in range(n + 1)]  # u 向上 2^j 条边的 (最大, 严格次大)

    depth[1], up[1][0], info[1][0] = 1, 0, (NEG, NEG)  # 根的父边哨兵
    queue = deque([1])
    while queue:
        u = queue.popleft()
        for v, w in adj[u]:
            if depth[v]:  # 已访问（父方向）
                continue
            depth[v] = depth[u] + 1
            up[v][0] = u
            info[v][0] = (w, NEG)  # 一条边没有次大
            queue.append(v)

    for j in range(1, LOG + 1):
        for i in range(1, n + 1):
            mid = up[i][j - 1]
            up[i][j] = up[mid][j - 1]
            info[i][j] = merge(info[i][j - 1], info[mid][j - 1])

    # ---- 3. 枚举非树边，换掉路径上「严格小于 w 的最大边」 ----
    def path_info(u: int, v: int) -> Info:
        """树上 u~v 路径的 (最大边权, 严格次大边权)。"""
        res: Info = (NEG, NEG)
        if depth[u] < depth[v]:
            u, v = v, u
        for j in range(LOG, -1, -1):  # u 跳到与 v 同层
            if depth[u] - depth[v] >= 1 << j:
                res = merge(res, info[u][j])
                u = up[u][j]
        if u == v:
            return res
        for j in range(LOG, -1, -1):  # 一起向上跳
            if up[u][j] != up[v][j]:
                res = merge(res, merge(info[u][j], info[v][j]))
                u, v = up[u][j], up[v][j]
        return merge(res, merge(info[u][0], info[v][0]))  # 补两条连向 LCA 的父边

    ans = -1  # 无解时保持 -1（题面保证存在，对拍覆盖无解情形）
    for u, v, w, in_mst in edges:
        if in_mst or u == v:  # 自环进不了任何生成树
            continue
        first, second = path_info(u, v)
        if w > first:
            cand = mst_sum - first + w  # 换最大边
        elif w == first and second != NEG:
            cand = mst_sum - second + w  # 换最大边增量 0，退到严格次大
        else:  # w < first 不可能发生；w == first 且无次大则该边无法严格替换
            continue
        ans = cand if ans < 0 or cand < ans else ans

    print(ans)


if __name__ == "__main__":
    solve()

复杂度

Kruskal：排序 $O(m \log m)$ 。
倍增表： $O(n \log n)$ 时间与空间。
枚举 $m$ 条非树边，每条一次 $O(\log n)$ 的路径查询： $O(m \log n)$ 。

总计 $O(m \log m)$ ，空间 $O(n \log n + m)$ 。 $n=10^5$ 、 $m=3\times10^5$ 下 C++ 实测约 0.3 秒。

总结

严格次小生成树的标准套路是「MST + 一次换边」：

正确性支点是交换论证：任何次小生成树都能归约成「与 MST 恰差一条边」的形态，因此枚举非树边就够；
每条非树边的最优换法是删掉 $u\sim v$ 路径上「严格小于 $w$ 的最大边」；
「严格」二字落在数据结构层，就是倍增表要同时维护最大与严格次大，合并时排除等值重复边——这是最容易写挂的地方，也是本题区分度的所在。

对拍验证：官方样例 in1 两个实现均输出 11；另用 gen.py 生成 300 组小图随机数据（ $3 \leqslant n \leqslant 8$ ，权值从 $\{0,1,2,3\}$ 小池抽取以制造大量重复，含重边、自环，并保底一条大权值弦保证有解），以 brute.cpp 枚举所有生成树为标准答案，main.cpp 与 main.py 均 AC 300/300。