「一本通 4.4 例 4」次小生成树

形式化题目

给定一个包含 $N$ 个顶点和 $M$ 条无向边的连通图 $G = (V, E)$ ，边权非负。设 $G$ 的最小生成树权值和为 $sum$ 。求所有权值和严格大于 $sum$ 的生成树中，权值和最小的一棵生成树的权值和。保证图连通、无自环，且必定存在严格次小生成树。

正解

思路

根据生成树与环的基本性质，严格次小生成树一定可以由某棵最小生成树（MST）通过替换恰好一条边得到：将一条不在 MST 中的非树边 $e = (u, v)$ 加入 MST 会形成唯一的简单环，若删去该环上（即原树中 $u$ 到 $v$ 的简单路径上）的一条树边 $e'$ ，即可得到一棵新的生成树。

新生成树的权值和为：

sum' = sum + w(e) - w(e')

为了使新生成树是严格次小生成树，必须满足：

严格大于： $w(e) > w(e')$ ，从而使得增量 $w(e) - w(e') > 0$ ；
最小增量：对于给定的非树边 $e$ ，希望减去的树边权值 $w(e')$ 尽量大，从而让增量尽量小。

因此，设树上 $u \to v$ 路径上的最大边权为 $m_1$ ，严格次大边权为 $m_2$ （若不存在则为 $-1$ ）：

若 $w(e) > m_1$ ：此时替换最大边 $m_1$ ，增量为 $w(e) - m_1$ ；
若 $w(e) = m_1$ ：此时替换 $m_1$ 增量为 $0$ （仍是最小生成树），不能产生严格更大的树；必须替换严格次大边 $m_2$ （要求 $m_2 \neq -1$ 且 $w(e) > m_2$ ），增量为 $w(e) - m_2$ 。

算法步骤：

使用 Kruskal 算法求出任意一棵最小生成树，并记录所有非树边。
以 1 号节点为根，通过 BFS 建立树上倍增表：
- 设 $LOGN = 18$ ；
- up[k][u] 表示节点 $u$ 的 $2^k$ 级祖先；
- f1[k][u] 表示 $u$ 到其 $2^k$ 级祖先路径上的最大边权；
- f2[k][u] 表示该路径上的严格次大边权。
- 在倍增向上合并两段路径时，将两段的最大值与次大值共 4 个候选值合并，去重并选出全局最大与严格次大。
遍历每条非树边 $(u, v, w)$ ，在倍增 LCA 的过程中同时合并并查询树上 $u \to v$ 路径的最大值 $m_1$ 与严格次大值 $m_2$ 。
按上述规则计算替换增量，取所有非树边中的最小增量 $\Delta_{min}$ 。
最终答案即为 $sum + \Delta_{min}$ 。

graph TD
    A[所有边按边权排序] --> B[Kruskal 构建最小生成树 MST]
    B --> C[BFS 遍历 MST 确定深度与直接父边]
    C --> D[倍增预处理 2^k 级祖先及路径最大/严格次大边权]
    D --> E[遍历所有非树边 e = u, v, w]
    E --> F[倍增 LCA 查询 u 到 v 路径上的 m1 与 m2]
    F --> G{w 与 m1 的关系}
    G -- w > m1 --> H[可用增量: w - m1]
    G -- w == m1 且 w > m2 --> I[可用增量: w - m2]
    H --> J[更新全局最小增量]
    I --> J
    J --> K[输出 MST 权值和 + 最小增量]

代码

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#!/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-05-22 19:17
# update_at: 2026-05-22 19:17

import sys

INF = 10**18


def combine(max1: int, max2: int, cand1: int, cand2: int) -> tuple[int, int]:
    """合并两条路径段的最大权与严格次大权。"""
    cands = {max1, max2, cand1, cand2} - {-1}
    m1 = max(cands) if cands else -1
    cands.discard(m1)
    m2 = max(cands) if cands else -1
    return m1, m2


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)

    # 读入所有边并按边权升序排序
    edges: list[tuple[int, int, int]] = []
    for _ in range(m):
        u = next(data)
        v = next(data)
        w = next(data)
        edges.append((w, u, v))
    edges.sort()

    # Kruskal 算法求最小生成树
    parent = list(range(n + 1))

    def find(i: int) -> int:
        path: list[int] = []
        while parent[i] != i:
            path.append(i)
            i = parent[i]
        for node in path:
            parent[node] = i
        return i

    mst_adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    non_mst_edges: list[tuple[int, int, int]] = []
    mst_weight = 0
    edges_count = 0

    for w, u, v in edges:
        root_u, root_v = find(u), find(v)
        if root_u != root_v:
            parent[root_u] = root_v
            mst_adj[u].append((v, w))
            mst_adj[v].append((u, w))
            mst_weight += w
            edges_count += 1
        else:
            non_mst_edges.append((w, u, v))

    # BFS 建立倍增表
    LOGN = 18
    up = [[0] * (n + 1) for _ in range(LOGN)]
    f1 = [[-1] * (n + 1) for _ in range(LOGN)]
    f2 = [[-1] * (n + 1) for _ in range(LOGN)]
    depth = [0] * (n + 1)

    # 从节点 1 开始 BFS
    queue = [1]
    depth[1] = 1
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        for v, w in mst_adj[u]:
            if not depth[v]:
                depth[v] = depth[u] + 1
                up[0][v] = u
                f1[0][v] = w
                queue.append(v)

    # 预处理 2^k 级祖先与路径上的最大/次大边权
    for k in range(LOGN - 1):
        up_k = up[k]
        up_next = up[k + 1]
        f1_k, f2_k = f1[k], f2[k]
        f1_next, f2_next = f1[k + 1], f2[k + 1]
        for v in range(1, n + 1):
            p = up_k[v]
            up_next[v] = up_k[p]
            f1_next[v], f2_next[v] = combine(f1_k[v], f2_k[v], f1_k[p], f2_k[p])

    def query_max(u: int, v: int) -> tuple[int, int]:
        """查询树上 u 到 v 路径上的最大边权与严格次大边权。"""
        m1, m2 = -1, -1
        if depth[u] < depth[v]:
            u, v = v, u

        # 提升 u 使 depth[u] == depth[v]
        diff = depth[u] - depth[v]
        for k in range(LOGN):
            if (diff >> k) & 1:
                m1, m2 = combine(m1, m2, f1[k][u], f2[k][u])
                u = up[k][u]

        if u == v:
            return m1, m2

        for k in range(LOGN - 1, -1, -1):
            if up[k][u] != up[k][v]:
                m1, m2 = combine(m1, m2, f1[k][u], f2[k][u])
                m1, m2 = combine(m1, m2, f1[k][v], f2[k][v])
                u = up[k][u]
                v = up[k][v]

        m1, m2 = combine(m1, m2, f1[0][u], f2[0][u])
        m1, m2 = combine(m1, m2, f1[0][v], f2[0][v])
        return m1, m2

    min_delta = INF
    for w, u, v in non_mst_edges:
        m1, m2 = query_max(u, v)
        if w > m1:
            diff = w - m1
            if diff < min_delta:
                min_delta = diff
        elif w > m2 and m2 != -1:
            diff = w - m2
            if diff < min_delta:
                min_delta = diff

    print(mst_weight + min_delta)


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/**
 * 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 08:03
 * update_at: 2026-10-05 08:03
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
const int MAXM = 300005;
const int LOGN = 18; // 2^17 > 1e5，满足倍增的最大跳跃需求
const ll INF = (1LL << 60);

struct Edge {
    int u;
    int v;
    int w; // 边权非负且不超过 1e9，用 int 存储；答案用 ll 累加
};
Edge edges[MAXM];    // 全部边，按边权升序排序后供 Kruskal 使用
Edge nonmst[MAXM];   // 不在最小生成树中的边，用于枚举替换
int non_cnt;

// 最小生成树的链式前向星：树上有 N-1 条边
int head[MAXN], to[2 * MAXN], nxt[2 * MAXN], edge_w[2 * MAXN], edge_cnt;

ll parent[MAXN]; // 并查集

// 倍增表：up[k][u] 为 u 的第 2^k 级祖先
// f1[k][u] / f2[k][u] 为 u 到该祖先路径上的最大边权与严格次大边权
int up[LOGN][MAXN];
int f1[LOGN][MAXN]; // 边权不超过 1e9，用 int 存储，-1 表示不存在
int f2[LOGN][MAXN];
int depth[MAXN];

int query_m1, query_m2; // 一次路径查询的结果：最大边权与严格次大边权

bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

ll find_root(ll x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // 路径折半压缩
        x = parent[x];
    }
    return x;
}

// 在最小生成树上加一条无向边。
void add_tree_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    edge_w[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 合并两段路径的最大边权与严格次大边权，结果写回 m1 / m2。
void merge_max(int &m1, int &m2, int c1, int c2) {
    int cand[4];
    cand[0] = m1;
    cand[1] = m2;
    cand[2] = c1;
    cand[3] = c2;
    int best1 = -1;
    int best2 = -1;
    for (int i = 0; i < 4; i++) {
        int x = cand[i];
        if (x < 0) {
            continue;
        }
        if (x > best1) {
            best2 = best1;
            best1 = x;
        } else if (x < best1 && x > best2) {
            best2 = x; // 严格次大：重复的相等值被跳过
        }
    }
    m1 = best1;
    m2 = best2;
}

// 查询树上 u 到 v 路径上的最大边权与严格次大边权。
void query_path(int u, int v) {
    int m1 = -1;
    int m2 = -1;
    if (depth[u] < depth[v]) {
        int t = u;
        u = v;
        v = t;
    }

    // 先把 u 提升到和 v 同深度
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOGN; k++) {
        if ((diff >> k) & 1) {
            merge_max(m1, m2, f1[k][u], f2[k][u]);
            u = up[k][u];
        }
    }

    if (u != v) {
        // 两端一起向上跳到 LCA 的下一层
        for (int k = LOGN - 1; k >= 0; k--) {
            if (up[k][u] != up[k][v]) {
                merge_max(m1, m2, f1[k][u], f2[k][u]);
                merge_max(m1, m2, f1[k][v], f2[k][v]);
                u = up[k][u];
                v = up[k][v];
            }
        }
        // 最后补上到 LCA 的两条边
        merge_max(m1, m2, f1[0][u], f2[0][u]);
        merge_max(m1, m2, f1[0][v], f2[0][v]);
    }

    query_m1 = m1;
    query_m2 = m2;
}

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

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    memset(head, 0, sizeof(head));
    memset(f1, -1, sizeof(f1)); // -1 表示该位置没有边
    memset(f2, -1, sizeof(f2));

    // Kruskal 求最小生成树，同时收集所有非树边
    ll mst_weight = 0;
    for (int i = 1; i <= m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        ll ru = find_root(u);
        ll rv = find_root(v);
        if (ru != rv) {
            parent[ru] = rv;
            add_tree_edge(u, v, w);
            add_tree_edge(v, u, w);
            mst_weight += w;
        } else {
            non_cnt++;
            nonmst[non_cnt].u = u;
            nonmst[non_cnt].v = v;
            nonmst[non_cnt].w = w;
        }
    }

    // 以 1 号点为根 BFS，确定深度并填好倍增第 0 层
    int queue_node[MAXN];
    int qhead = 0;
    int qtail = 0;
    depth[1] = 1;
    queue_node[qtail] = 1;
    qtail++;
    while (qhead < qtail) {
        int u = queue_node[qhead];
        qhead++;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (depth[v] == 0) {
                depth[v] = depth[u] + 1;
                up[0][v] = u;
                f1[0][v] = edge_w[i];
                queue_node[qtail] = v;
                qtail++;
            }
        }
    }

    // 自底向上构造倍增表
    for (int k = 0; k + 1 < LOGN; k++) {
        for (int v = 1; v <= n; v++) {
            int p = up[k][v];
            up[k + 1][v] = up[k][p];
            f1[k + 1][v] = f1[k][v];
            f2[k + 1][v] = f2[k][v];
            merge_max(f1[k + 1][v], f2[k + 1][v], f1[k][p], f2[k][p]);
        }
    }

    // 枚举每条非树边，用替换一条树边的最小正增量更新答案
    ll min_delta = INF;
    for (int i = 1; i <= non_cnt; i++) {
        int u = nonmst[i].u;
        int v = nonmst[i].v;
        int w = nonmst[i].w;
        query_path(u, v);
        if (w > query_m1) {
            ll delta = w - query_m1;
            if (delta < min_delta) {
                min_delta = delta;
            }
        } else if (query_m2 != -1 && w > query_m2) {
            ll delta = w - query_m2;
            if (delta < min_delta) {
                min_delta = delta;
            }
        }
    }

    printf("%lld\n", mst_weight + min_delta);

    return 0;
}

复杂度

时间复杂度： $O(M \log M + M \log N)$
- 边权排序耗时 $O(M \log M)$ ，并查集构建 MST 耗时 $O(M \alpha(N))$ ；
- 树上倍增表预处理耗时 $O(N \log N)$ ；
- 查询 $M - N + 1$ 条非树边对应的路径最值，单次倍增 LCA 耗时 $O(\log N)$ ，总计 $O(M \log N)$ 。整个算法在 $N \le 10^5, M \le 3 \times 10^5$ 下运行平稳高效。
空间复杂度： $O(N \log N + M)$
- 存储图结构与非树边需要 $O(N + M)$ 空间；
- 倍增数组 up, f1, f2 各需 $18 \times N$ 的空间，约几万至几十万元素，完全满足 128MB 限制。

总结

严格次小生成树是最小生成树的经典扩展，关键在于认清生成树加边成环后的单边替换原理。对于“严格”的要求，本质是规避边权相等带来的非正增量，通过在树上倍增时同时维护最大值与严格次大值，可以在 $O(\log N)$ 内精准得到合法替换边，将问题高效解决。

「一本通 4.4 例 4」次小生成树

目录

形式化题目

正解

思路

代码

复杂度

总结