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

题目解析

证明: 看 _严格次小生成树证明与算法.md
- 点评: 比较难的证明
代码: 比较长,用到了
- 集合合并: 最大与最小的合并的证明
- 倍增: binary jump ,(当然这是倍增里的证明) : 快速跳(数数)到可行区域的最后一个

对严格次小算法的感觉

这确实是一个**“结论易懂、代码套路、但证明极深”**的知识点。在算法竞赛（NOI/ICPC/CSP-S）的语境下，你的感觉是非常敏锐的。

对于选手来说，面对“严格次小生成树”，确实存在**“应试策略”和“学术理解”**的区别。

以下是针对竞赛选手的掌握建议：

一、竞赛中是如何考查这个知识点的？

在比赛中，出题人考查严格次小生成树，通常不会直接让你写数学证明，而是通过以下几个维度来“为难”你：

1. 代码实现的准确度（尤其是“严格”二字）

这是最大的坑。

考点：很多题目要求“严格”次小。
陷阱：如果不小心，代码写成了“非严格次小”（即允许 $w(T') = w(T)$ ）。
具体表现：当非树边权值 $w_{new}$ 等于路径最大值 $max1$ 时，如果你直接忽略了，或者没有维护 $max2$ （严格次大值），你的程序就会输出错误的答案（输出了 MST 的权值，或者没找到真正的次小）。
难度：在于倍增数组维护 max2 时的逻辑细节，写起来很繁琐，容易写挂。

2. 数据结构能力的结合

考点：题目往往不会只考裸的 $N=1000$ ，而是 $N=10^5$ 或 $N=3 \times 10^5$ 。
意图：这逼迫你不能用 $O(N)$ 暴力扫路径，必须熟练掌握 LCA + 倍增（Binary Lifting） 或者 树链剖分（HLD） 来维护区间最大/次大值。
本质：这道题披着图论的外衣，实际上是在考查你在树上高效查询信息的能力。

3. 图论性质的综合应用

有时候题目不会直接说“求次小生成树”，而是问：
- “对于每条边，如果必须包含它，MST 的权值是多少？”
- “判断 MST 是否唯一？”（如果次小生成树权值等于 MST 权值，则 MST 不唯一）。
- 这些问题本质上都是“换边法”的变形。

二、只要“记住结论”就可以了吗？

对于 90% 的题目：是的，记住结论和模板就够了。

你只需要牢牢记住以下三句话，就能通过绝大多数相关题目：

次小生成树一定是在 MST 的基础上，换一条边得到的。（这就决定了枚举非树边的思路）
严格次小需要维护路径上的“最大值”和“严格次大值”。（这是代码实现的各种细节核心）
非树边 $w_{new}$ 替换掉的，一定是环上比它小的最大那条边。

那剩下的 10% 为什么需要理解证明？ 因为只有理解了证明（尤其是那个“环路性质”），你才能应对变种题。比如：

动态加边/删边：如果题目问你动态维护次小生成树（利用 LCT），单纯背静态结论可能就会卡住，你需要理解“环被切断”的本质。
特殊图：如果是在基环树或仙人掌图上做类似操作，你需要明白“换边”本质上是利用了环的性质，从而迁移思路。

三、选手应该如何掌握？（分级指南）

针对你现在的阶段（正在钻研图论进阶），建议按以下步骤掌握：

Level 1: 模板级掌握（必须做到）

不要纠结于复杂的数学反证法，先把代码写对。

目标：能够不看题解，独立写出 Luogu P4180 [BJWC2010] 严格次小生成树。
重点：
- LCA 倍增数组的预处理。
- query(u, v, w_new) 函数的编写：如何在两条路径（ $u \to lca$ , $v \to lca$ ）合并时，正确计算出相对于 $w_new$ 的最大替换值。
- 排雷：一定要处理好 long long（权值和可能会爆 int）。

Level 2: 理解“最大”与“次大”的必要性

思考：为什么一定要维护 max2？
场景：自己手画一个简单的图（比如一个三角形， $A-B$ 边权1， $B-C$ 边权1， $A-C$ 边权1）。MST 权值是2。非树边权值也是1。
悟道：如果不维护 max2，你会发现无法替换（因为 $1-1=0$ ，没有增量），但实际上可能不存在严格次小生成树（输出 -1）。或者在边权为 $1, 2, 2$ 的时候，非树边为 2，你需要找比 2 小的边来换。

Level 3: 直觉化证明（最高境界）

不需要你会写形式化证明，但要有这种直觉：

“MST 是最紧凑的骨架。任何一根多余的线（非树边）搭上去，都会形成一个圈。为了不让圈存在，我必须拆掉圈里一根最脆弱（权值最大）的骨头。为了让总重增加最少，我要拆掉的那根骨头，必须尽可能接近我新搭上去的那根线。”

总结

算法竞赛不是数学竞赛。

对于证明：大概知道是用“反证法”和“拟阵交换性质”保证的即可，不必深究每一步不等式。
对于代码：LCA 倍增维护最大/次大值 的 merge 操作是核心基本功，这部分代码必须写得像呼吸一样自然。

核心思路解析

什么是次小生成树？

次小生成树（Second MST）是指在无向图中，权值和排在第二位的生成树。通常可以通过“换边法”得到：

先求出最小生成树（MST）。
对于每一条不在 MST 中的边 $(u, v)$ （权值为 $w$ ），把它加入 MST 会形成一个环。
为了变回树，我们需要断开环上除了 $(u, v)$ 以外的一条边。为了让新树的权值尽可能小，我们要断开环上权值最大的一条边（记为 $max\_w$ ）。
新的权值 = $MST权值 - max\_w + w$ 。
什么是“严格”次小？

题目要求新树的权值严格大于 MST 的权值。

即： $MST权值 - val_{removed} + w > MST权值 \Rightarrow w > val_{removed}$ 。

3. 算法流程：

求 MST：使用 Kruskal 算法求出 MST，记录总权值 sum，并标记哪些边是 MST 的边。
建树与预处理 (LCA + 倍增)：
- 在 MST 上建立邻接表。
- 使用倍增法（Doubling）维护 LCA。
- 关键点：除了维护第 $2^i$ 代祖先 fa[u][i]，还要维护：
  - mx[u][i]：从 $u$ 到 $fa[u][i]$ 路径上的最大边权。
  - secmx[u][i]：从 $u$ 到 $fa[u][i]$ 路径上的严格次大边权。
枚举非树边：
- 遍历所有没有被加入 MST 的边 $(u, v)$ ，权值为 $w$ 。
- 在 MST 上找到 $u$ 和 $v$ 之间的路径，查询路径上的最大值 $m_1$ 和严格次大值 $m_2$ 。
- 判断逻辑：
  - 如果 $w > m_1$ ：这是一个合法的替换。候选答案 = sum - m1 + w。
  - 如果 $w == m_1$ ：换掉最大边会导致权值不变（非严格次小），所以必须换掉严格次大边。候选答案 = sum - m2 + w。
输出最小的候选答案。

代码

cpp

copy

        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
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-03 20:15:14
 * Modified for Strictly Second MST
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 1e5+5; // 题目范围 N<=10^5
const int maxe = 3e5+5; // M<=3*10^5
const ll INF64 = 1e18;  // 用于初始化次大值
const int INF = 2e9; 
int n, m;
ll mst_res;

// 边的结构体
struct Edge {
    int u, v;
    long long w;
    int id;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

// Kruskal 算法封装
struct KruskalAlgorithm {
    struct DSU {
        std::vector<int> fa;
        void init(int n) {
            fa.resize(n + 1);
            std::iota(fa.begin(), fa.end(), 0);
        }
        int find(int x) {
            return x == fa[x] ? x : fa[x] = find(fa[x]);
        }
        bool merge(int x, int y) {
            int fx = find(x), fy = find(y);
            if (fx == fy) return false;
            fa[fx] = fy;
            return true;
        }
    } dsu;

    int n;
    std::vector<Edge> edges;
    std::vector<bool> in_mst; // 标记边是否在 MST 中

    void init(int _n, int _m) {
        n = _n;
        edges.clear();
        dsu.init(n);
        in_mst.assign(_m + 1, false);
    }

    void add_edge(int u, int v, long long w, int id) {
        edges.push_back({u, v, w, id});
    }

    long long solve() {
        std::sort(edges.begin(), edges.end());
        dsu.init(n);
        long long ans = 0;
        int cnt = 0;
        for (const auto& e : edges) {
            if (dsu.merge(e.u, e.v)) {
                ans += e.w;
                cnt++;
                in_mst[e.id] = true; // 标记这条边是树边
            }
            if (cnt == n - 1) break;
        }
        if (cnt < n - 1) return -1;
        return ans;
    }
} kruskal;

// 链式前向星
struct linkList {
    struct edge { int u, v, w, next; };
    edge e[maxe * 2]; // 无向图双向边，大小要翻倍
    int h[maxn], edge_cnt;
    linkList() { edge_cnt = 0; memset(h, -1, sizeof(h)); }
    void add(int u, int v, int w = 0) { 
        e[edge_cnt] = {u, v, w, h[u]}; h[u] = edge_cnt++; 
    }
    void add2(int u, int v, int w = 0) {
        add(u, v, w); add(v, u, w);
    }
    edge & operator[](int id) { return e[id]; }
} e;

const int MAXLOG = 18; // 2^18 > 100000

// 核心工具：合并两个区间的最值信息
// 返回 {最大值, 严格次大值}
pair<int, int> merge_info(pair<int, int> a, pair<int, int> b) {
    // 收集所有可能的候选值
    int c[4] = {a.first, a.second, b.first, b.second};
    int mx = -INF, se = -INF;
    
    // 找最大值
    for(int i=0; i<4; ++i) mx = max(mx, c[i]);
    
    // 找严格次大值 (必须严格小于 mx)
    for(int i=0; i<4; ++i) {
        if (c[i] < mx) {
            se = max(se, c[i]);
        }
    }
    return {mx, se};
}

struct LCA {
    int f[maxn][MAXLOG + 1];
    int mx[maxn][MAXLOG + 1]; // 区间最大值
    int se[maxn][MAXLOG + 1]; // 区间严格次大值
    int d[maxn];

    void init(int n, int root) {
        // 1. DFS 预处理深度、父亲和第一级边权
        dfs(root, 0, 1, -INF); // 根节点的父边权值设为 -INF

        // 2. 倍增预处理
        for (int j = 1; j <= MAXLOG; ++j) {
            for (int i = 1; i <= n; ++i) {
                f[i][j] = f[f[i][j - 1]][j - 1];
                
                // 关键：合并 [i, 2^(j-1)] 和 [2^(j-1), 2^j] 两段的信息
                pair<int, int> info = merge_info(
                    {mx[i][j-1], se[i][j-1]},
                    {mx[f[i][j-1]][j-1], se[f[i][j-1]][j-1]}
                );
                mx[i][j] = info.first;
                se[i][j] = info.second;
            }
        }
    }

    // DFS 增加 w_from_fa 参数：这是连接 u 和 fa 的边的权值
    void dfs(int u, int fa, int depth, int w_from_fa) {
        d[u] = depth;
        f[u][0] = fa;
        mx[u][0] = w_from_fa;
        se[u][0] = -INF; // 一条边没有次大值，初始化为无穷小
        
        for (int i = e.h[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            int w = e[i].w;
            if (v != fa) {
                dfs(v, u, depth + 1, w);
            }
        }
    }

    // 查询 u 到 v 路径上的 {最大值, 严格次大值}
    // 注意：这里不需要求 LCA 点本身，只需要路径上的边权信息
    pair<int, int> ask_path_info(int u, int v) {
        pair<int, int> res = {-INF, -INF};
        
        // 保证 u 是 深度深的那个
        if (d[u] < d[v]) swap(u, v);

        // 1. u 向上跳到和 v 同层
        for (int i = MAXLOG; i >= 0; --i) {
            if (d[u] - (1 << i) >= d[v]) {
                // 合并 u 跳跃过程中的最值
                res = merge_info(res, {mx[u][i], se[u][i]});
                u = f[u][i];
            }
        }

        if (u == v) return res;

        // 2. u 和 v 一起向上跳
        for (int i = MAXLOG; i >= 0; --i) {
            if (f[u][i] != f[v][i]) {
                res = merge_info(res, {mx[u][i], se[u][i]});
                res = merge_info(res, {mx[v][i], se[v][i]});
                u = f[u][i];
                v = f[v][i];
            }
        }

        // 3. 最后还要加上连接 LCA 的那两条边 (u->LCA, v->LCA)
        res = merge_info(res, {mx[u][0], se[u][0]});
        res = merge_info(res, {mx[v][0], se[v][0]});
        
        return res;
    }
} lca;

void init() {
    std::cin >> n >> m;
    kruskal.init(n, m);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        ll w;
        std::cin >> u >> v >> w;
        kruskal.add_edge(u, v, w, i);
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    init();
    
    // 1. 求 MST
    mst_res = kruskal.solve();

    // 2. 构建 MST 图 (仅包含树边)
    // 你的 Kruskal 结构体里有一个 in_mst 数组，这很好
    for (const auto& ke : kruskal.edges) {
        if (kruskal.in_mst[ke.id]) {
            e.add2(ke.u, ke.v, ke.w); // 注意这里要把权值 ke.w 传进去！
        }
    }

    // 3. LCA 初始化 (倍增预处理最值)
    // 注意：数据可能不连通(虽然题目保证有解)，通常以 1 为根
    lca.init(n, 1);

    ll ans = INF64; // 严格次小生成树的权值

    // 4. 遍历所有 非树边
    for (const auto& ke : kruskal.edges) {
        if (!kruskal.in_mst[ke.id]) {
            int u = ke.u;
            int v = ke.v;
            ll w = ke.w;
            
            // 特判：如果是自环，忽略
            if (u == v) continue;

            // 查询树上路径 u -> v 的最大值和严格次大值
            pair<int, int> info = lca.ask_path_info(u, v);
            int max1 = info.first;
            int max2 = info.second;

            //  
            // 此时 u-v 这条非树边和树上路径构成了环
            // 我们要尝试用 w 替换掉环上的一条边
            
            if (w > max1) {
                // 如果非树边比路径最大边大，直接替换最大边
                ans = min(ans, mst_res - max1 + w);
            } else if (w == max1) {
                // 如果相等，说明替换最大边得不到"严格"次小
                // 必须退而求其次，替换严格次大边
                if (max2 != -INF) { // 确保存在次大边
                    ans = min(ans, mst_res - max2 + w);
                }
            }
            // 注意：w < max1 是不可能的，否则 T 就不是 MST 了
        }
    }
    
    // 输出结果
    cout << ans << endl;

    return 0;
}

目录