「一本通 3.1 练习 6」次小生成树

形式化题目

给定 $n$ 个点、 $m$ 条边的无向连通图，无自环，边权非负且不超过 $10^9$ 。设最小生成树的边权和为 $S$ ，求所有边权和严格大于 $S$ 的生成树中权值和最小者，输出该权值和。数据保证严格次小生成树存在。

样例的图与两棵候选生成树的关键边如下（实线为 MST 边，虚线为落选的非树边）：

graph G {
    node [shape=circle, style=filled, fillcolor=lightblue];
    1 [label="1"]; 2 [label="2"]; 3 [label="3"]; 4 [label="4"]; 5 [label="5"];
    1 -- 2 [label="1"];
    1 -- 3 [label="2"];
    2 -- 4 [label="3"];
    3 -- 5 [label="4"];
    3 -- 4 [label="3", style=dashed, color=red];
    4 -- 5 [label="6", style=dashed, color=gray];
    label="样例图：实线 = MST 边（S=10），红虚线 = 非树边 3-4，灰虚线 = 非树边 4-5";
    labelloc=t;
}

MST 为 $\{1\text{-}2(1),\ 1\text{-}3(2),\ 2\text{-}4(3),\ 3\text{-}5(4)\}$ ， $S = 10$ ；落选的非树边只有 $3$ - $4$ （权 $3$ ）和 $4$ - $5$ （权 $6$ ）。读者应观察到：两条虚线边各自与实线边构成一个环，"删环上哪条边"决定了候选答案——这正是全文要解决的问题。

正解

思路

朴素想法与瓶颈。 先用 Kruskal 求出一棵 MST $T$ 、边权和 $S$ 。其余生成树怎么找？任取一条非树边 $e = (u, v, w)$ 加进 $T$ ，会形成一个环（ $e$ 加上 $T$ 里 $u$ 到 $v$ 的路径 $P$ ），删掉 $P$ 上任意一条边 $f$ 就得到一棵新生成树，权值和为 $S + w - w(f)$ 。于是朴素做法是：枚举每条非树边，再从 $u$ 沿父链一路爬到 $v$ ，逐条扫描路径边找"可删的最大边"。单次扫描 $O(n)$ ，总计 $O(nm)$ ，在 $n, m$ 达 $10^5 / 3 \times 10^5$ 时不可行。瓶颈明确：静态树上、按权值上界求路径可删边的快速查询。

关键观察：为什么严格性是本题的坑。 枚举非树边换边之所以够用，是因为可以证明严格次小生成树一定能由 MST 单次换边得到（见"正确性"，本质是交换引理 + “MST 最优 ⇒ 每次换边权值不减”）。对单条 $e = (u, v, w)$ ：

要新树权值和严格大于 $S$ ，必须 $w(f) < w$ ；要最小，就在满足条件的边里取权值最大的那条。
由 $T$ 最优可知 $P$ 上最大边权 $M \leqslant w$ （否则换掉 $M$ 得到更小的生成树，矛盾）。所以：
- $M < w$ ：删最大边 $M$ ；
- $M = w$ ：删严格小于 $w$ 的最大边，即路径的严格次大值（若整条路径都不小于 $w$ ，这条非树边无贡献）。

样例里非树边 $3$ - $4$ （ $w = 3$ ）的路径 $3$ - $1$ - $2$ - $4$ 边权为 $2, 3, 3$ ，最大值恰好等于 $w$ ：删掉 $3$ 只会得到 $10$ ，不严格；必须删 $2$ ，候选 $= 10 + 3 - 2 = 11$ 。这就是必须同时维护"最大 + 严格次大"的原因。

倍增把查询压到 $O(\log n)$ 。 DFS 定根后，对每个点 $v$ 预处理 $2^k$ 级祖先 up[k][v]，以及 $v$ 到该祖先这段路径上的最大边权 mx[k][v] 和严格小于它的次大边权 m2[k][v]。两段首尾相接时的合并规则是：

(m_1, m_2) \oplus (n_1, n_2) = \Big(\max(m_1, n_1),\ \max\{\,x \in \{m_1, m_2, n_1, n_2\} \mid x < \max(m_1, n_1)\,\}\Big)

即"谁不是合并后的最大值，谁就有资格当次大候选"：本段最大值等于全局最大时只能用本段次大顶上。该运算可结合，"次大 $<$ 最大"的不变量始终保持。查询时先把深的一侧抬到同一深度（深度差的二进制位决定每一级跳不跳），再从高位向低位试探 up[k][a] != up[k][b]，两侧同步跳跃并合并经过的段，最后各爬一步到 LCA，整条路径的 $(M, \text{second})$ 就出来了。

逐条换边取最小。 对每条非树边算出 $(M, \text{second})$ 后，令 $\text{cut} = M$ （当 $M < w$ ）否则 $\text{second}$ ；cut = -1 表示没有严格小于 $w$ 的路径边，跳过；否则候选为 $S + w - \text{cut}$ 。所有候选取 $\min$ 即答案。样例的完整推演：

非树边	$T$ 上 $u$ - $v$ 路径边权	严格小于 $w$ 的最大边	候选权值和
$3$ - $4$ （ $w=3$ ）	$3$ - $1$ - $2$ - $4$ ： $2, 3, 3$	$2$	$10 + 3 - 2 = 11$
$4$ - $5$ （ $w=6$ ）	$4$ - $2$ - $1$ - $3$ - $5$ ： $3, 1, 2, 4$	$4$	$10 + 6 - 4 = 12$

两行取 $\min$ 得 $11$ ，与样例输出一致；注意第一行若按朴素直觉"删最大边"会算出 $10$ ，恰好不严格。

正确性小结。 设 $T'$ 是严格次小生成树， $A = T' \setminus T$ 、 $B = T \setminus T'$ 。对每条 $a \in A$ ， $T + a$ 的唯一环必含 $B$ 的边（否则 $T'$ 自带环），交换引理可把 $A$ 与 $B$ 一一配对；由 $T$ 最优，每个配对的增量 $w(a) - w(b) \geqslant 0$ ，故 $\text{sum}(T') - S$ 是若干非负增量之和且为正，其中至少一个正增量不大于它——对应一次严格改进的单次换边不劣于 $T'$ 。因此枚举所有非树边的最优换边并取 $\min$ ，恰好得到严格次小生成树；而每次换边的最优删边就是上文按 $M < w$ / $M = w$ 分类选出的 $\text{cut}$ 。

代码

Python 版：

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146#!/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-09-30 14:40
# update_at: 2026-09-30 14:40

import sys

NEG = -1    # 哨兵：这一段路径上不存在"更小的第二条边"（边权非负，-1 必小于任何真实边权）
LOG = 17    # 倍增层数：2^17 = 131072 > 1e5，覆盖全部点数
INF = 10**18  # 答案初始值：边权和上限 3e5 * 1e9 = 3e14


def find(fa: list[int], x: int) -> int:
    """并查集查根：隔代路径压缩，把查询路径直接挂到根下。"""
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x


def merge_top2(left: tuple[int, int], right: tuple[int, int]) -> tuple[int, int]:
    """合并两段路径，得到并集的 (最大边权, 严格小于最大的次大边权)。"""
    big = left[0] if left[0] > right[0] else right[0]
    # 谁不是最大值，谁才可能当次大：本段最大值等于全局最大时，只能用本段的次大顶上
    cand_l = left[0] if left[0] < big else left[1]
    cand_r = right[0] if right[0] < big else right[1]
    return big, cand_l if cand_l > cand_r else cand_r


def kruskal(
    edges: list[tuple[int, int, int]], n: int
) -> tuple[int, list[list[tuple[int, int]]], list[tuple[int, int, int]]]:
    """按 (权值, 端点) 升序贪心：选中的边写进生成树邻接表，落选的边就是候选替换边。"""
    fa = list(range(n))
    g: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    light: list[tuple[int, int, int]] = []
    total = 0
    edges.sort()
    for w, a, b in edges:
        ra, rb = find(fa, a), find(fa, b)
        if ra != rb:
            fa[ra] = rb
            total += w
            g[a].append((b, w))
            g[b].append((a, w))
        else:
            light.append((a, b, w))
    return total, g, light


def build_lifting(
    g: list[list[tuple[int, int]]],
) -> tuple[list[int], list[list[int]], list[list[int]], list[list[int]]]:
    """从 0 号点定根 DFS，建倍增表：up 是 2^k 级祖先，mx/m2 是对应段的最大/严格次大边权。"""
    n = len(g)
    depth = [0] * n
    parent = [-1] * n        # -1 表示还没访问过
    w0 = [NEG] * n           # 到父节点的边权，根节点没有
    parent[0] = 0
    stack = [0]
    while stack:
        a = stack.pop()
        for b, w in g[a]:
            if parent[b] < 0:
                parent[b] = a
                w0[b] = w
                depth[b] = depth[a] + 1
                stack.append(b)

    up = [parent]
    mx = [w0]
    m2 = [[NEG] * n]         # 单条边的段里没有第二条边可当次大
    for _ in range(1, LOG):
        prev_up, prev_mx, prev_m2 = up[-1], mx[-1], m2[-1]
        cur_up, cur_mx, cur_m2 = [0] * n, [0] * n, [0] * n
        for v in range(n):
            p = prev_up[v]
            cur_up[v] = prev_up[p]  # 2^(k-1) 级祖先再跳 2^(k-1) 级 = 2^k 级祖先
            cur_mx[v], cur_m2[v] = merge_top2(
                (prev_mx[v], prev_m2[v]), (prev_mx[p], prev_m2[p])
            )
        up.append(cur_up)
        mx.append(cur_mx)
        m2.append(cur_m2)
    return depth, up, mx, m2


def path_top2(
    u: int,
    v: int,
    depth: list[int],
    up: list[list[int]],
    mx: list[list[int]],
    m2: list[list[int]],
) -> tuple[int, int]:
    """求树上 u-v 路径的 (最大边权, 严格小于最大的次大边权)：两侧分别爬升、分段合并。"""
    a, b = u, v
    seg_u = (NEG, NEG)  # u 一侧已经爬过的路径段
    seg_v = (NEG, NEG)  # v 一侧已经爬过的路径段
    if depth[a] < depth[b]:
        a, b = b, a

    diff = depth[a] - depth[b]
    for k in range(LOG):
        if diff >> k & 1:  # 深度差的二进制位决定每一级跳不跳
            seg_u = merge_top2(seg_u, (mx[k][a], m2[k][a]))
            a = up[k][a]

    if a != b:  # 还没相遇，从高倍增位往下试，能分开跳就一起跳
        for k in range(LOG - 1, -1, -1):
            if up[k][a] != up[k][b]:
                seg_u = merge_top2(seg_u, (mx[k][a], m2[k][a]))
                seg_v = merge_top2(seg_v, (mx[k][b], m2[k][b]))
                a = up[k][a]
                b = up[k][b]
        # 此时两点的父节点就是 LCA，最后各爬一步把末段收进来
        seg_u = merge_top2(seg_u, (mx[0][a], m2[0][a]))
        seg_v = merge_top2(seg_v, (mx[0][b], m2[0][b]))
    return merge_top2(seg_u, seg_v)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    edges: list[tuple[int, int, int]] = []
    for _ in range(m):
        x, y, z = next(data), next(data), next(data)
        edges.append((z, x - 1, y - 1))  # 0-based 下标，按 (权值, 端点) 存，排序即 Kruskal 顺序

    mst_sum, g, light_edges = kruskal(edges, n)
    depth, up, mx, m2 = build_lifting(g)

    best = INF
    for a, b, w in light_edges:
        big, second = path_top2(a, b, depth, up, mx, m2)
        # 最小生成树最优 ⇒ 路径最大边权必 ≤ w；要让总权严格变大，只能删掉路径上严格小于 w 的最大边
        cut = big if big < w else second
        if cut >= 0:  # -1 表示整条路径都不小于 w，这次替换换不出更大的权值和
            best = min(best, mst_sum + w - cut)
    print(best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234/**
 * 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-05 04:18
 * update_at: 2026-10-05 04:18
 */

// 严格次小生成树
// 先用 Kruskal 求出一棵最小生成树 T、边权和 S；每加一条非树边 e=(u,v,w) 就形成一个环，
// 删掉环上一条边即可得到新生成树，权值为 S + w - w(f)。
// 要严格大于 S，就必须删掉环上严格小于 w 的最大边：路径最大边权 M < w 时删 M，
// M == w 时只能删严格次大值。于是对 MST 做倍增，维护树上每段路径的（最大边权，严格次大边权），
// 每条非树边用 O(log n) 查一次，所有候选取 min。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005;  // 点数上限
const int MAXM = 300005;  // 边数上限
const int LOG = 17;       // 2^17 = 131072 > 1e5，覆盖任意两点的深度差与倍增跳跃
const ll NEG = -1;        // 哨兵：边权非负，-1 必小于任何真实边权，表示"这样的边不存在"

int n, m;

struct Edge {
    int u;
    int v;
    ll w;
};

Edge edges[MAXM];        // 全部边，排序后跑 Kruskal
Edge light_edges[MAXM];  // 落选的非树边，建好倍增表后逐条换边
int light_cnt;

int fa[MAXN];  // 并查集父节点

// 最小生成树的邻接表（链式前向星），最多 n-1 条边，所以开 2*MAXN
int head[MAXN];
int to[2 * MAXN];
int nxt[2 * MAXN];
ll edge_w[2 * MAXN];
int edge_cnt;

// 建倍增表用的树信息
int parent[MAXN];       // 每个点在 DFS 树上的父节点，0 表示还没访问
ll w_to_parent[MAXN];   // 每个点到父节点的边权
int depth[MAXN];        // 到根的边数
int stk[MAXN];          // 手写 DFS 栈，避免深度 1e5 时递归爆栈
int up[LOG][MAXN];      // up[k][v]：v 的 2^k 级祖先
ll mx[LOG][MAXN];       // mx[k][v]：v 向上跳 2^k 步这段路径上的最大边权
ll m2[LOG][MAXN];       // m2[k][v]：该段中严格小于 mx 的最大边权，NEG 表示不存在

// 一段树上路径的（最大边权，严格小于最大边权的次大边权）
struct Top2 {
    ll big;
    ll second;
};

Top2 make_top2(ll big, ll second) {
    Top2 t;
    t.big = big;
    t.second = second;
    return t;
}

// 合并两段首尾相接的路径：谁不是合并后的最大值，谁就有资格当次大候选；
// 本段最大值正好等于全局最大值时，只能用本段次大顶上。
Top2 merge_top2(Top2 a, Top2 b) {
    Top2 res;
    res.big = a.big > b.big ? a.big : b.big;
    ll cand_a = a.big < res.big ? a.big : a.second;
    ll cand_b = b.big < res.big ? b.big : b.second;
    res.second = cand_a > cand_b ? cand_a : cand_b;
    return res;
}

// 边按 (权值, 端点) 升序，用于 Kruskal
bool cmp_edge(const Edge &a, const Edge &b) {
    if (a.w != b.w) return a.w < b.w;
    if (a.u != b.u) return a.u < b.u;
    return a.v < b.v;
}

// 并查集查找，带路径压缩
int find_root(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

// 给 MST 加一条无向边，正反两个方向各存一次
void add_edge(int u, int v, ll w) {
    edge_cnt++;
    to[edge_cnt] = v;
    edge_w[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;

    edge_cnt++;
    to[edge_cnt] = u;
    edge_w[edge_cnt] = w;
    nxt[edge_cnt] = head[v];
    head[v] = edge_cnt;
}

// 以 1 号点为根迭代 DFS，求出每个点的父节点、到父节点的边权与深度
void dfs_build_root() {
    for (int v = 1; v <= n; v++) {
        parent[v] = 0;
    }
    int top = 0;
    stk[++top] = 1;
    parent[1] = 1;           // 根指向自己，方便倍增里祖先的比较
    w_to_parent[1] = NEG;    // 根没有到父节点的边
    depth[1] = 0;
    while (top > 0) {
        int u = stk[top--];
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (parent[v] == 0) {
                parent[v] = u;
                w_to_parent[v] = edge_w[e];
                depth[v] = depth[u] + 1;
                stk[++top] = v;
            }
        }
    }
}

// 建倍增表：第 k 层 = 从 v 跳 2^(k-1) 步到 mid，再接上 mid 跳 2^(k-1) 步的那一段
void build_lifting() {
    for (int v = 1; v <= n; v++) {
        up[0][v] = parent[v];
        mx[0][v] = w_to_parent[v];
        m2[0][v] = NEG;  // 只有一条边的段里没有第二条边可当次大
    }
    for (int k = 1; k < LOG; k++) {
        for (int v = 1; v <= n; v++) {
            int mid = up[k - 1][v];
            up[k][v] = up[k - 1][mid];
            Top2 t = merge_top2(make_top2(mx[k - 1][v], m2[k - 1][v]),
                                make_top2(mx[k - 1][mid], m2[k - 1][mid]));
            mx[k][v] = t.big;
            m2[k][v] = t.second;
        }
    }
}

// 查树上 u-v 路径的（最大边权，严格次大边权）：两侧分别爬升，边走边合并经过的段
Top2 path_top2(int u, int v) {
    Top2 side_u = make_top2(NEG, NEG);  // u 一侧已爬过的路径段
    Top2 side_v = make_top2(NEG, NEG);  // v 一侧已爬过的路径段
    int a = u;
    int b = v;
    if (depth[a] < depth[b]) {
        int tmp = a;
        a = b;
        b = tmp;
    }

    // 先把深的一侧抬到同一深度：深度差的二进制位决定每一级跳不跳
    int diff = depth[a] - depth[b];
    for (int k = 0; k < LOG; k++) {
        if ((diff >> k) & 1) {
            side_u = merge_top2(side_u, make_top2(mx[k][a], m2[k][a]));
            a = up[k][a];
        }
    }

    if (a != b) {
        // 还没相遇，从高倍增位往低试，祖先不同就两侧一起跳
        for (int k = LOG - 1; k >= 0; k--) {
            if (up[k][a] != up[k][b]) {
                side_u = merge_top2(side_u, make_top2(mx[k][a], m2[k][a]));
                side_v = merge_top2(side_v, make_top2(mx[k][b], m2[k][b]));
                a = up[k][a];
                b = up[k][b];
            }
        }
        // 此时 a、b 的父节点就是 LCA，最后各爬一步把末段收进来
        side_u = merge_top2(side_u, make_top2(mx[0][a], m2[0][a]));
        side_v = merge_top2(side_v, make_top2(mx[0][b], m2[0][b]));
    }
    return merge_top2(side_u, side_v);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%lld", &edges[i].u, &edges[i].v, &edges[i].w);
    }
    sort(edges + 1, edges + m + 1, cmp_edge);

    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    ll mst_sum = 0;  // 最小生成树的边权和 S
    light_cnt = 0;
    for (int i = 1; i <= m; i++) {
        int ru = find_root(edges[i].u);
        int rv = find_root(edges[i].v);
        if (ru != rv) {
            fa[ru] = rv;
            mst_sum += edges[i].w;
            add_edge(edges[i].u, edges[i].v, edges[i].w);
        } else {
            light_cnt++;
            light_edges[light_cnt] = edges[i];
        }
    }

    dfs_build_root();
    build_lifting();

    ll best = NEG;  // -1 表示还没找到严格更大的生成树
    for (int i = 1; i <= light_cnt; i++) {
        ll w = light_edges[i].w;
        Top2 t = path_top2(light_edges[i].u, light_edges[i].v);
        // MST 最优 ⇒ 路径最大边权必 ≤ w；要让总权严格变大，只能删路径上严格小于 w 的最大边
        ll cut = t.big < w ? t.big : t.second;
        if (cut < 0) continue;  // 整条路径的边都不小于 w，这条非树边换不出更大的权值和
        ll cand = mst_sum + w - cut;
        if (best < 0 || cand < best) best = cand;
    }
    printf("%lld\n", best);

    return 0;
}

复杂度

时间复杂度： $O(m \log m + n \log n + (m - n + 1) \log n) = O((n + m) \log n)$ 。排序主导 Kruskal，建表 $O(n \log n)$ ，每条非树边一次 $O(\log n)$ 查询。
空间复杂度： $O(n \log n + m)$ 。倍增表 3 张 $\times 17$ 层 $\times n$ ，加边表与邻接表； $2^{17} = 131072 > 10^5$ 。C++ 实现远小于 128MB；Python 因对象开销实测峰值约 200MB，算法阶数与 C++ 正解一致。

总结

严格次小生成树 = 在 MST 上对每条非树边做一次"最优换边"，所有严格改进的候选取 $\min$ 。
边权可以相等，所以必须同时维护路径的（最大边权，严格次大边权）： $M = w$ 时删最大边不严格，只能删严格次大。
倍增把"路径上最大 / 严格次大"的查询从 $O(n)$ 压到 $O(\log n)$ ，整体 $O((n + m) \log n)$ 与 C++ 正解同阶；Python 实现允许 TLE/MLE，但算法不退化为暴力。

图示解析

下图展示从读入到输出的完整求解流水线，以及"严格"分支在哪里起作用：

flowchart TD
    A[读入 n, m 与 m 条边] --> B[Kruskal: 按权值升序 + 并查集]
    B --> C[MST 边权和 S 与 MST 邻接表]
    B --> D[落选边 = 候选非树边]
    C --> E[DFS 定根建倍增表 up/mx/m2]
    E --> F[对每条非树边查询路径 M 与严格次大 second]
    D --> F
    F --> G{M < w ?}
    G -- 是 --> H[cut = M]
    G -- 否 M = w --> I[cut = second]
    I --> J{second = -1 ?}
    J -- 是 --> K[该边无严格改进, 跳过]
    J -- 否 --> L[candidate = S + w - cut]
    H --> L
    L --> M[所有候选取 min]
    K --> N[输出答案]
    M --> N

读者应重点看 M < w ? 这个分支：它就是"严格次小"区别于"非严格次小"的全部细节—— $M = w$ 时必须落到 second，否则算出的候选等于 $S$ ，会被题目要求的"严格大于"排除。