本课时有配套视频讲解，购买后即可观看（永久有效）

求次小生成树

一、课上练习

编程练习

次小生成树：L49983

二、知识总结

✨ 核心思想

次小生成树是指在所有生成树中，权值之和严格大于最小生成树（或等于，取决于题意是严格次小还是非严格次小）的权值最小的生成树。

核心思路：在最小生成树的基础上，枚举替换一条边——去掉 MST 中的一条边，加入一条非 MST 边，使得新的生成树权值尽可能小。

✨ 算法原理

方法：枚举非树边替换

先求出最小生成树（Kruskal 算法）。
建 MST 的树结构，预处理树上任意两点路径上的最大边权和严格次大边权（使用倍增 LCA）。
枚举每条非树边 $(u, v, w)$ $(u, v, w)$ ：
- 在 MST 上找到 $u \to v$ 路径上的最大边权 $\text{maxW}$ 。
- 如果 $w > \text{maxW}$ ，则替换后权值增加 $w - \text{maxW}$ 。
- 如果 $w = \text{maxW}$ （求严格次小生成树时），则需要找路径上的严格次大边权 $\text{secW}$ ，替换后增加 $w - \text{secW}$ 。
取所有替换方案中增量最小的，即为次小生成树。

为什么只需替换一条边？

定理：次小生成树与最小生成树恰好相差一条边。即：去掉 MST 的某一条边，加入某一条非 MST 边，就能得到次小生成树。

倍增预处理路径最大/次大值

在 MST 上使用倍增（Binary Lifting）预处理：

maxVal[u][k]：从 $u$ 向上走 $2^k$ 步路径上的最大边权。
secVal[u][k]：路径上的严格次大边权。

查询 $u \to v$ 的最大/次大值时，沿 LCA 路径合并即可。

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5const int MAXM = 300005;
6const int LOG = 17;
7const long long INF = 1e18;
8
9struct Edge {
10    int u, v;
11    long long w;
12    bool inMST; // 是否在MST中
13    bool operator<(const Edge& o) const { return w < o.w; }
14};
15
16Edge edges[MAXM];
17int fa[MAXN], rk[MAXN]; // 并查集
18int n, m;
19
20// MST 的邻接表
21vector<pair<int, long long>> adj[MAXN];
22
23// 倍增 LCA
24int dep[MAXN], par[MAXN][LOG];
25long long maxVal[MAXN][LOG]; // 路径最大值
26long long secVal[MAXN][LOG]; // 路径严格次大值
27
28int find(int x) {
29    if (fa[x] != x) fa[x] = find(fa[x]);
30    return fa[x];
31}
32
33bool unite(int x, int y) {
34    int fx = find(x), fy = find(y);
35    if (fx == fy) return false;
36    if (rk[fx] < rk[fy]) swap(fx, fy);
37    fa[fy] = fx;
38    if (rk[fx] == rk[fy]) rk[fx]++;
39    return true;
40}
41
42// BFS建树，计算深度和父节点
43void bfs(int root) {
44    queue<int> q;
45    dep[root] = 0;
46    par[root][0] = root;
47    maxVal[root][0] = -INF;
48    secVal[root][0] = -INF;
49    q.push(root);
50    vector<bool> vis(n + 1, false);
51    vis[root] = true;
52    while (!q.empty()) {
53        int u = q.front(); q.pop();
54        for (auto [v, w] : adj[u]) {
55            if (vis[v]) continue;
56            vis[v] = true;
57            dep[v] = dep[u] + 1;
58            par[v][0] = u;
59            maxVal[v][0] = w;
60            secVal[v][0] = -INF;
61            q.push(v);
62        }
63    }
64    // 倍增预处理
65    for (int k = 1; k < LOG; k++) {
66        for (int u = 1; u <= n; u++) {
67            int anc = par[u][k - 1];
68            par[u][k] = par[anc][k - 1];
69            // 合并两段的最大和次大
70            long long vals[4] = {maxVal[u][k-1], secVal[u][k-1],
71                                 maxVal[anc][k-1], secVal[anc][k-1]};
72            maxVal[u][k] = -INF;
73            secVal[u][k] = -INF;
74            for (long long v : vals) {
75                if (v > maxVal[u][k]) {
76                    secVal[u][k] = maxVal[u][k];
77                    maxVal[u][k] = v;
78                } else if (v != maxVal[u][k] && v > secVal[u][k]) {
79                    secVal[u][k] = v;
80                }
81            }
82        }
83    }
84}
85
86// 查询u到v路径上的最大值和严格次大值
87pair<long long, long long> query(int u, int v) {
88    long long mx = -INF, smx = -INF;
89    // 辅助函数：用val更新mx和smx
90    auto upd = [&](long long val) {
91        if (val > mx) { smx = mx; mx = val; }
92        else if (val != mx && val > smx) smx = val;
93    };
94    if (dep[u] < dep[v]) swap(u, v);
95    int diff = dep[u] - dep[v];
96    for (int k = 0; k < LOG; k++) {
97        if ((diff >> k) & 1) {
98            upd(maxVal[u][k]);
99            upd(secVal[u][k]);
100            u = par[u][k];
101        }
102    }
103    if (u == v) return {mx, smx};
104    for (int k = LOG - 1; k >= 0; k--) {
105        if (par[u][k] != par[v][k]) {
106            upd(maxVal[u][k]); upd(secVal[u][k]);
107            upd(maxVal[v][k]); upd(secVal[v][k]);
108            u = par[u][k]; v = par[v][k];
109        }
110    }
111    upd(maxVal[u][0]); upd(maxVal[v][0]);
112    upd(secVal[u][0]); upd(secVal[v][0]);
113    return {mx, smx};
114}
115
116int main() {
117    ios::sync_with_stdio(false);
118    cin.tie(nullptr);
119
120    cin >> n >> m;
121    for (int i = 1; i <= n; i++) { fa[i] = i; rk[i] = 0; }
122    for (int i = 0; i < m; i++) {
123        cin >> edges[i].u >> edges[i].v >> edges[i].w;
124        edges[i].inMST = false;
125    }
126
127    sort(edges, edges + m);
128
129    // 求MST
130    long long mstWeight = 0;
131    int cnt = 0;
132    for (int i = 0; i < m && cnt < n - 1; i++) {
133        if (unite(edges[i].u, edges[i].v)) {
134            edges[i].inMST = true;
135            mstWeight += edges[i].w;
136            adj[edges[i].u].push_back({edges[i].v, edges[i].w});
137            adj[edges[i].v].push_back({edges[i].u, edges[i].w});
138            cnt++;
139        }
140    }
141
142    // 建树并预处理LCA
143    bfs(1);
144
145    // 枚举非树边，求次小生成树
146    long long ans = INF;
147    for (int i = 0; i < m; i++) {
148        if (edges[i].inMST) continue;
149        auto [mx, smx] = query(edges[i].u, edges[i].v);
150        long long w = edges[i].w;
151        if (w > mx) {
152            ans = min(ans, mstWeight - mx + w);
153        } else if (smx != -INF) {
154            // w == mx 时，用严格次大值替换
155            ans = min(ans, mstWeight - smx + w);
156        }
157    }
158
159    cout << ans << endl;
160    return 0;
161}

✨ 执行示例

假设有 4 个顶点、5 条边：

边：(1,2,1) (1,3,2) (2,3,3) (2,4,4) (3,4,5)

Kruskal 求 MST：选 (1,2,1)、(1,3,2)、(2,4,4)，总权值 = 7。
非树边：(2,3,3) 和 (3,4,5)。
枚举替换：
- 加入 (2,3,3)：路径 2→3 上最大边权为 max(1,2)=2，替换后 7 - 2 + 3 = 8。
- 加入 (3,4,5)：路径 3→4 上最大边权为 max(2,1,4)=4，替换后 7 - 4 + 5 = 8。
次小生成树权值 = 8。

✨ 解题步骤详解

Kruskal 求 MST：标记哪些边在 MST 中。
建树：用 MST 的边建邻接表，作为树结构。
倍增预处理：BFS 求深度和父节点，预处理路径最大/次大值。
枚举非树边：对每条非树边查询替换的增量，取最小增量。
区分严格/非严格：严格次小需要处理等权边的情况，使用次大值。

✨ 常见错误

未区分严格与非严格次小生成树：严格次小要求权值严格大于 MST，需要维护次大值。
倍增合并最大/次大时逻辑错误：合并两段时必须同时考虑两段的最大和次大，取全局最大和严格次大。
LCA 查询时忘记最后一步：跳到 LCA 下方后，还需要把最后一步的边权也纳入考虑。
INF 设置不当：次大值初始应为 $-\infty$ ，表示不存在。
权值溢出：总权值计算用 long long。

✨ 算法评价

指标	分析
时间复杂度	$O(E \log E + E \log V)$ ，Kruskal 排序 + 倍增 LCA 查询
空间复杂度	$O(V \log V + E)$ ，倍增表 + 边存储
适用场景	需要求严格/非严格次小生成树的题目
实现难度	较高，需要同时掌握 Kruskal、LCA 倍增

次小生成树是最小生成树的经典拓展题，是竞赛中的高频考点。