[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

/**
 * 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;
}