我的算法书 - 严格次小生成树

一句话算法

严格次小生成树先求一棵 MST，再枚举每条非树边，尝试替换它在 MST 路径上的最大边或严格次大边。

问题模型

给定一张无向连通带权图，求权值和严格大于最小生成树、且在所有满足条件的生成树中权值最小的一棵生成树。

“严格”表示答案必须满足：

w(T') > w(MST)

如果只得到相同权值的另一棵 MST，不算严格次小生成树。

核心直觉

先固定一棵 MST。任意加入一条非树边 $(u,v,w)$ ，MST 中 $u$ 到 $v$ 的路径会和这条新边形成一个环。

要重新变成生成树，必须从这个环里删掉一条边。为了让新树尽量小，应该删掉路径上能删的最大边。

但严格次小生成树有一个细节：

如果非树边权 $w$ 大于路径最大边，删最大边即可。
如果 $w$ 等于路径最大边，删它只会得到同权 MST，不严格；此时要尝试删路径上小于 $w$ 的最大边，也就是严格次大边。

算法步骤

用 Kruskal 求出一棵 MST，记录 MST 权值和 mst，并标记哪些边被选入 MST。
把 MST 边建成一棵树。
在 MST 树上做倍增预处理：
- up[k][u]：点 u 向上跳 $2^k$ 步到达的祖先；
- mx1[k][u]：这段路径上的最大边权；
- mx2[k][u]：这段路径上严格小于最大值的次大边权。
枚举每条非树边 $(u,v,w)$ ：
- 查询 MST 中 $u$ 到 $v$ 路径上的最大边 largest 和严格次大边 second_largest；
- 若 largest < w，候选答案为 mst + w - largest；
- 否则若 second_largest < w，候选答案为 mst + w - second_largest；
- 否则这条边不能产生严格更大的生成树。
所有候选取最小值。

算法证明

关键结论： 存在一棵严格次小生成树，可以由某棵 MST 只换一条边得到。

加入非树边必成环

MST 是树。向树中加入任意一条非树边 $(u,v)$ ，一定在 $u$ 到 $v$ 的树路径上形成唯一环。
一次换边保持生成树

在这个环中删去任意一条原 MST 边，图重新变成 $n-1$ 条边且连通，因此仍是生成树。
候选树覆盖最优解

设 $T'$ 是一棵严格次小生成树。比较 $T'$ 和 MST，取 $T'$ 中任意一条不在 MST 中的边 $e$ 。把 $e$ 加入 MST 后形成一个环。这个环上至少有一条 MST 边不在 $T'$ 中，删去其中合适的一条可以得到另一棵生成树。

MST 的最小性保证，单次换边得到的增量不会比 $T'$ 的总增量更差。因此枚举所有非树边的单次换边候选，必然能覆盖严格次小生成树的最优答案。
为什么要维护次大边

若非树边权等于路径最大边，删最大边得到的权值仍为 mst，不满足严格大于。此时必须找路径上严格小于它的最大边，才能得到最小的正增量。

所以算法正确。

复杂度分析

Kruskal 排序复杂度为 $O(m\log m)$ 。

倍增预处理复杂度为 $O(n\log n)$ 。

每条非树边查询路径最大/次大边复杂度为 $O(\log n)$ ，总复杂度为：

O(m\log m+m\log n)

空间复杂度为 $O(n\log n+m)$ 。

代码实现

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
235
236
237
238
239
240

        #include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;    // 点数上限，按题面 n <= 10^5
const int MAXM = 300005;    // 边数上限，按题面 m <= 3*10^5
const int MAXLG = 18;       // 倍增层数上限，2^17 > 10^5
const int MAXE = 2 * MAXN;  // MST 只有 n-1 条边，按双向存共 2(n-1) 条

const ll INF = (1LL << 62);
const ll NEG = -(1LL << 60);  // “这条路径上没有这种边”的哨兵，边权必须大于它

// 一条无向边：从 u 连到 v，边权 w
struct Edge {
    int u;  // 起点
    int v;  // 终点
    ll w;   // 边权
};

Edge edge_list[MAXM];  // edge_list[i]：读入的第 i 条边（下标从 0 开始）
bool in_mst[MAXM];     // in_mst[i]：第 i 条边是否被 Kruskal 选进 MST

int dsu_parent[MAXN];  // dsu_parent[x]：x 的父节点，x 是根时等于 x
int dsu_size[MAXN];    // dsu_size[x]：x 是根时集合的大小，按大小合并用

int head[MAXN];        // 链式前向星：head[u] 是从 u 出发的第一条 MST 树边
int tree_to[MAXE];     // 这条树边指向的点
int tree_nxt[MAXE];    // 同一出发点的下一条树边
ll tree_weight[MAXE];  // 这条树边的边权
int tree_edge_cnt;     // 已加入的树边条数

int depth[MAXN];          // depth[u]：u 在 MST 上的深度，根为 1
int up[MAXLG][MAXN];      // up[k][u]：u 向上跳 2^k 步到达的点
ll mx1[MAXLG][MAXN];      // mx1[k][u]：这段路径上的最大边权
ll mx2[MAXLG][MAXN];      // mx2[k][u]：这段路径上严格小于最大值的次大边权

int n;  // 点数
int m;  // 边数

// 边权小的排在前面，Kruskal 每次都先试当前最小的边。
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

void dsu_init(int n) {
    for (int i = 1; i <= n; i++) {
        dsu_parent[i] = i;
        dsu_size[i] = 1;
    }
}

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent[x]);
    return dsu_parent[x];
}

// 合并 a、b 所在的两个集合；两端本来就连通时返回 false。
bool dsu_merge(int a, int b) {
    int root_a = dsu_find(a);
    int root_b = dsu_find(b);
    if (root_a == root_b) return false;
    // 小集合接到大集合下面，配合路径压缩，单次操作接近常数。
    if (dsu_size[root_a] < dsu_size[root_b]) swap(root_a, root_b);
    dsu_parent[root_b] = root_a;
    dsu_size[root_a] += dsu_size[root_b];
    return true;
}

// 在 MST 上连一条无向边 u--v，边权为 w。
void add_tree_edge(int u, int v, ll w) {
    tree_edge_cnt++;
    tree_to[tree_edge_cnt] = v;
    tree_weight[tree_edge_cnt] = w;
    tree_nxt[tree_edge_cnt] = head[u];
    head[u] = tree_edge_cnt;
}

// 用 Kruskal 求最小生成树，同时把选中的边建成树。
// 返回 MST 的总权值；图不连通时返回 -1。
ll build_mst() {
    sort(edge_list, edge_list + m, cmp_edge);
    dsu_init(n);

    ll total = 0;      // MST 的总权值
    int selected = 0;  // 已选边数，一棵生成树正好要 n - 1 条

    for (int i = 0; i < m && selected < n - 1; i++) {
        // 自环、两端已经连通的边都会成环，不能选。
        if (!dsu_merge(edge_list[i].u, edge_list[i].v)) continue;
        in_mst[i] = true;
        total += edge_list[i].w;
        selected++;
        add_tree_edge(edge_list[i].u, edge_list[i].v, edge_list[i].w);
        add_tree_edge(edge_list[i].v, edge_list[i].u, edge_list[i].w);
    }

    if (selected != n - 1) return -1;
    return total;
}

// 在 MST 上递归，预处理每个点的深度、父亲和到父亲的边权。
void dfs_tree(int u, int parent_node) {
    for (int i = head[u]; i != 0; i = tree_nxt[i]) {
        int v = tree_to[i];
        if (v == parent_node) continue;
        depth[v] = depth[u] + 1;
        up[0][v] = u;
        mx1[0][v] = tree_weight[i];
        mx2[0][v] = NEG;  // 只有一条边，没有次大边
        dfs_tree(v, u);
    }
}

// 把候选值 x 合并进“最大边 largest / 严格次大边 second_largest”这一对里。
// 只有严格小于当前最大值才可能当次大边，所以最大的边永远进不了第二位。
void add_candidate(ll x, ll &largest, ll &second_largest) {
    if (x == NEG) return;
    if (x > largest) {
        second_largest = largest;
        largest = x;
    } else if (x < largest && x > second_largest) {
        second_largest = x;
    }
}

// 把「u 向上跳 2^k 步」这段路径上的最大、次大边权合并进 (largest, second_largest)。
void merge_segment(int k, int u, ll &largest, ll &second_largest) {
    add_candidate(mx1[k][u], largest, second_largest);
    add_candidate(mx2[k][u], largest, second_largest);
}

// 倍增预处理：up、mx1、mx2 三张表。
void build_lca() {
    // 全局数组默认是 0，而 0 也是合法边权，所以先全部设成“不存在”哨兵。
    for (int k = 0; k < MAXLG; k++) {
        for (int u = 0; u <= n; u++) {
            mx1[k][u] = NEG;
            mx2[k][u] = NEG;
        }
    }

    depth[1] = 1;
    up[0][1] = 0;
    dfs_tree(1, 0);

    for (int k = 1; k < MAXLG; k++) {
        for (int u = 1; u <= n; u++) {
            int mid = up[k - 1][u];  // 先跳 2^(k-1) 步，到达中点
            up[k][u] = up[k - 1][mid];
            mx1[k][u] = NEG;
            mx2[k][u] = NEG;
            // 前半段和后半段各贡献两个候选值，合并成这一段的最大、次大边权。
            merge_segment(k - 1, u, mx1[k][u], mx2[k][u]);
            merge_segment(k - 1, mid, mx1[k][u], mx2[k][u]);
        }
    }
}

// 查询 MST 上 a 到 b 的路径：最大边权 largest 与严格次大边权 second_largest。
void path_max_two(int a, int b, ll &largest, ll &second_largest) {
    largest = NEG;
    second_largest = NEG;

    // 先把深的点跳到和另一个点同深度。
    if (depth[a] < depth[b]) swap(a, b);
    int diff = depth[a] - depth[b];
    for (int k = 0; k < MAXLG; k++) {
        if (diff >> k & 1) {
            merge_segment(k, a, largest, second_largest);
            a = up[k][a];
        }
    }

    if (a == b) return;  // 其中一个点就是祖先，路径已经走完

    // 两个点一起往上跳，直到它们的父亲相同。
    for (int k = MAXLG - 1; k >= 0; k--) {
        if (up[k][a] != up[k][b]) {
            merge_segment(k, a, largest, second_largest);
            merge_segment(k, b, largest, second_largest);
            a = up[k][a];
            b = up[k][b];
        }
    }

    // 最后各补一条到 LCA 的边。
    merge_segment(0, a, largest, second_largest);
    merge_segment(0, b, largest, second_largest);
}

void read_input() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edge_list[i].u >> edge_list[i].v >> edge_list[i].w;
    }
}

void solve() {
    ll mst_total = build_mst();
    if (mst_total < 0) {  // 图不连通，不存在生成树
        cout << -1 << '\n';
        return;
    }

    build_lca();

    ll answer = INF;
    for (int i = 0; i < m; i++) {
        if (in_mst[i]) continue;  // 只枚举非树边

        // 加入非树边会成环，只能删环上的一条边才能变回生成树。
        // 删严格小于它的最大边，才能让总权值严格变大且增量最小。
        ll largest, second_largest;
        path_max_two(edge_list[i].u, edge_list[i].v, largest, second_largest);

        ll removed = NEG;
        if (largest < edge_list[i].w) removed = largest;
        else if (second_largest < edge_list[i].w) removed = second_largest;

        if (removed != NEG) {
            answer = min(answer, mst_total + edge_list[i].w - removed);
        }
    }

    if (answer == INF) cout << -1 << '\n';  // 所有非树边都换不出严格更大的生成树
    else cout << answer << '\n';
}

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

    read_input();
    solve();

    return 0;
}

Python

哨兵 NEG = -(1 << 60) 沿用 C++，因此边权须大于它。接口是 strict_second_mst(n, edges)，无生成树或无严格次小生成树时返回 -1；find 与建树遍历都写成迭代，因为长链的深度会爆 Python 递归限制（C++ 版直接递归）。

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
147
148
149
150
151
152
153
154
155
156
157
158
159

        # 严格次小生成树：点编号 1..n，边表是 (u, v, w) 三元组。
# strict_second_mst 返回严格次小生成树权值；无生成树或无严格次小生成树时返回 -1。
# 做法：先 Kruskal 求 MST，再倍增维护树上路径的「最大、严格次大」边权，
# 最后枚举每条非树边做一次换边。边权须大于 NEG；Python 的 int 不会溢出。

import sys
from collections.abc import Iterable

NEG = -(1 << 60)  # 「不存在」哨兵，须小于任何合法边权
INF = 1 << 62     # 答案上界哨兵，须大于任何合法答案

type Edge = tuple[int, int, int]        # (起点 u, 终点 v, 边权 w)
type Pair = tuple[int, int]             # (最大边权, 严格次大边权)，缺失分量是 NEG
type Tbl = list[list[int]]              # 一张倍增表：第 k 行是跳 2^k 步的信息
type Adj = list[list[tuple[int, int]]]  # tree[u] = [(邻点 v, 边权 w), ...]
type Prepared = tuple[list[int], Tbl, Tbl, Tbl]  # (depth, up, mx1, mx2) 四张倍增表


def find(parent: list[int], x: int) -> int:
    """找 x 所在集合的根，顺路把路径上的点挂到根上（迭代压缩，不受递归深度限制）。"""
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root


def two_largest(values: Iterable[int]) -> Pair:
    """候选边权里的最大与严格次大：重复值只留一份，缺失分量取 NEG。"""
    largest = second = NEG
    for x in values:
        if x > largest:
            largest, second = x, largest
        elif second < x < largest:
            second = x
    return largest, second


def mst_edges(n: int, edges: list[Edge]) -> set[int] | None:
    """Kruskal：返回被选入 MST 的边下标集合；图不连通时返回 None。"""
    parent = list(range(n + 1))
    size = [1] * (n + 1)
    chosen: set[int] = set()

    for i in sorted(range(len(edges)), key=lambda i: edges[i][2]):  # 边权小的先试
        u, v, _ = edges[i]
        root_u, root_v = find(parent, u), find(parent, v)
        if root_u == root_v:  # 两端已经连通，选它就会成环
            continue
        if size[root_u] < size[root_v]:  # 小集合接到大集合下面
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        chosen.add(i)
        if len(chosen) == n - 1:  # 生成树正好 n - 1 条边，选满就停
            break
    return chosen if len(chosen) == n - 1 else None


def prepare_lca(n: int, tree: Adj) -> Prepared:
    """倍增预处理：depth[u] 是深度，up[k][u] 跳 2^k 步，mx1/mx2 是这一段的最大/次大边权。"""
    lg = max(1, n.bit_length())  # 最小的使 2^lg > n 的幂次，n = 1 时 lg = 1
    depth = [0] * (n + 1)
    up = [[0] * (n + 1) for _ in range(lg)]
    # 两表分开存顶点权重的整数，比每格存一个 (最大, 次大) 元组省下大量元组头开销。
    mx1 = [[NEG] * (n + 1) for _ in range(lg)]
    mx2 = [[NEG] * (n + 1) for _ in range(lg)]

    # 建树遍历用显式栈：树链最坏 n 深，递归会爆 Python 栈；树无环，靠父节点挡回头路。
    depth[1] = 1  # 根深度从 1 起，点 0 是「祖先不存在」的黑洞
    stack = [1]
    while stack:
        u = stack.pop()
        for v, w in tree[u]:
            if v == up[0][u]:
                continue
            depth[v] = depth[u] + 1
            up[0][v] = u
            mx1[0][v] = w  # 只往上走一步，没有次大边（mx2 保持 NEG）
            stack.append(v)

    for k in range(1, lg):
        for u in range(1, n + 1):
            mid = up[k - 1][u]  # 先跳 2^(k-1) 步到达中点，把前后两段的最值合起来
            up[k][u] = up[k - 1][mid]
            mx1[k][u], mx2[k][u] = two_largest(
                (mx1[k - 1][u], mx2[k - 1][u], mx1[k - 1][mid], mx2[k - 1][mid])
            )

    return depth, up, mx1, mx2


def path_max_two(a: int, b: int, prepared: Prepared) -> Pair:
    """树上 a-b 路径的 (最大边权, 严格次大边权)；缺失分量用 NEG。"""
    depth, up, mx1, mx2 = prepared
    answer: Pair = (NEG, NEG)

    if depth[a] < depth[b]:
        a, b = b, a
    for k in range(len(up)):
        if (depth[a] - depth[b]) >> k & 1:  # 差的二进制第 k 位为 1 就跳 2^k 步
            answer = two_largest((*answer, mx1[k][a], mx2[k][a]))
            a = up[k][a]

    if a == b:  # 其中一个点是另一个的祖先，路径已经走完
        return answer

    for k in range(len(up) - 1, -1, -1):
        if up[k][a] != up[k][b]:  # 还没跳到 LCA 就两个点一起往上跳
            answer = two_largest((*answer, mx1[k][a], mx2[k][a], mx1[k][b], mx2[k][b]))
            a, b = up[k][a], up[k][b]

    # 此时 a、b 是 LCA 的两个孩子，再补上各自到 LCA 的那条边。
    return two_largest((*answer, mx1[0][a], mx2[0][a], mx1[0][b], mx2[0][b]))


def strict_second_mst(n: int, edges: list[Edge]) -> int:
    """返回严格次小生成树权值；无生成树或无严格次小生成树时返回 -1。"""
    chosen = mst_edges(n, edges)
    if chosen is None:  # 图不连通，没有生成树
        return -1

    tree: Adj = [[] for _ in range(n + 1)]
    mst = 0
    for i in chosen:
        u, v, w = edges[i]
        mst += w
        tree[u].append((v, w))
        tree[v].append((u, w))

    prepared = prepare_lca(n, tree)

    answer = INF
    for i, (u, v, w) in enumerate(edges):
        if i in chosen:  # 树边不能替换自己
            continue
        largest, second_largest = path_max_two(u, v, prepared)
        # 要严格变小只能删严格小于 w 的边：优先删最大，最大等于 w 时退而求次大。
        removed = NEG
        if largest < w:
            removed = largest
        elif second_largest < w:
            removed = second_largest
        if removed != NEG:
            answer = min(answer, mst + w - removed)

    return -1 if answer == INF else answer


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    edges: list[Edge] = [(next(data), next(data), next(data)) for _ in range(m)]
    print(strict_second_mst(n, edges))


if __name__ == "__main__":
    solve()

测试用例

输入：

输出：

解释：MST 权值为 3，加入边 1-3(2) 并替换路径上的一条权值 1 的边，得到严格次小生成树权值 4。

应用分类详解

严格次小生成树的本质是“在 MST 基础上求最小正增量”。

一、严格次小生成树模板

典型模式： 题面明确要求严格次小生成树。

识别信号： “严格次小”“权值严格大于 MST”“第二小生成树”。

核心建模： 先求 MST，再枚举非树边做一次换边。

应用场景	经典题目	核心思路
严格次小生成树模板	luogu-P4180	Kruskal + 倍增维护路径最大/次大边

二、MST 敏感性分析

典型模式： 分析替换某条边后生成树权值如何变化。

识别信号： “加入一条边”“删除一条边”“MST 是否唯一”。

核心建模： 非树边加入后只影响一条树上路径；比较路径最大边即可。

应用场景	经典题目	核心思路
MST 唯一性判断	生成树唯一性题	若存在同权替换边，则 MST 不唯一
边权扰动分析	图论构造题	计算每条非树边的换边增量

经典例题

1. luogu-P4180

严格次小生成树模板题。核心难点不是 Kruskal，而是路径查询时必须维护最大边和严格次大边，避免同权替换得到非严格答案。

2. MST 唯一性判断

如果存在一条非树边，其权值等于 MST 路径上的最大边，那么可以做同权替换，说明 MST 不唯一。

3. 生成树边权增量分析

枚举非树边并查询路径最大边，可以得到把这条边强制加入生成树时的最小增量。

参考

Kruskal 最小生成树
倍增 LCA