题目题解：严格次小生成树

题目描述

给定一个带权无向图，求其严格次小生成树。严格次小生成树定义为总权值严格大于最小生成树，且在所有满足条件的生成树中权值最小的那棵。

算法思路

1. Kruskal求最小生成树：首先用Kruskal算法求出最小生成树（MST），并记录所有未被选中的边（非树边）。
2. 预处理树上路径极值：在MST上预处理每个节点到祖先路径上的最大边权和次大边权（严格小于最大值）。
3. 枚举非树边：对每条非树边(u, v, w)，找到MST中u→v路径上的最大边权max_val：
4. 若max_val < w：替换后总权值为MST总权值 - max_val + w
5. 若max_val == w：需要替换路径上的次大边权sec_max_val（必须严格小于max_val）
6. 维护答案：对所有可能替换方案取最小值。

代码分块解释

1. 树的构建与DFS预处理

vector<pair<int,int>> to[N]; 
int maxn[N][21]; // 向上2^j步的最大边权
int maxnn[N][21]; // 向上2^j步的次大边权
int dep[N]; // 节点深度

void dfs(int x, int pre) {
    dep[x] = dep[pre] + 1;
    fa[x] = pre; // 这里的fa[]被重新赋值为父节点
    for (auto t : to[x]) {
        int v = t.first, val = t.second;
        if (v == pre) continue;
        maxn[v][0] = val; // 直接到父节点的边权
        dfs(v, x);
    }
}

2. LCA的二进制倍增预处理

int dp[N][21]; // 向上2^j步的祖先节点

// LCA预处理
for (int j = 0; j <= 20; j++) {
    if (j == 0) {
        for (int x = 1; x <= n; x++) 
            dp[x][j] = fa[x]; // fa[x]已通过DFS赋值为父节点
    } else {
        for (int x = 1; x <= n; x++) 
            dp[x][j] = dp[dp[x][j-1]][j-1];
    }
}

3. 路径最大/次大边权预处理

for (int j = 1; j <= 20; j++) {
    for (int x = 1; x <= n; x++) {
        int parent = dp[x][j-1];
        // 情况1：两段最大值相等
        if (maxn[x][j-1] == maxn[parent][j-1]) {
            maxn[x][j] = maxn[x][j-1];
            // 合并次大值候选：当前段和父节点段的次大值
            set<int> s = {maxnn[x][j-1], maxnn[parent][j-1]};
            maxnn[x][j] = s.size() >= 2 ? *(++s.rbegin()) : 0;
        } 
        // 情况2：两段最大值不等
        else {
            maxn[x][j] = max(maxn[x][j-1], maxn[parent][j-1]);
            // 次大值为较小最大值 或 两段的次大值中的较大者
            int smaller_max = min(maxn[x][j-1], maxn[parent][j-1]);
            int larger_sec = max(maxnn[x][j-1], maxnn[parent][j-1]);
            maxnn[x][j] = max(smaller_max, larger_sec);
        }
    }
}

• dp 预处理每个节点向上2^j步路径的最大值maxn和次大值maxnn。

4. 主函数处理流程

signed main() {
    // 读入边并排序
    sort(edge.begin(), edge.end());

    // Kruskal求MST
    for (遍历边) {
        if (边不连通) 加入MST，累加边权;
        else 加入n_edge（非树边）;
    }

    // DFS预处理
    dfs(1, 1);

    // LCA和极值预处理
    预处理dp数组、maxn、maxnn;

    // 枚举非树边求答案
    for (auto& e : n_edge) {
        int u = e.second.first, v = e.second.second, w = e.first;
        int anc = lca(u, v);

        // 收集u->anc和v->anc路径上的极值
        set<int> path_vals;
        通过二进制跳跃收集路径上的maxn和maxnn;

        // 计算替换后的权值
        int max_val = 路径最大值;
        if (max_val < w) 更新ANS;
        else if (存在次大值) 用次大值更新;
    }
    cout << ANS;
}

• 关键步骤：
• 使用Kruskal算法求MST，同时分离非树边。
• 通过DFS初始化每个节点的父节点和深度。
• 二进制预处理LCA和路径极值。
• 对每条非树边，找到其在树中的路径，计算替换后的权值。

复杂度分析

• 时间复杂度：
• Kruskal算法：O(m log m)
• DFS和预处理：O(n log n)
• 处理非树边：每条边O(log n)
• 总复杂度：O(m log m + n log n)
• 空间复杂度：O(n log n)，用于存储二进制跳跃表。

可以通过的代码

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll;
#define int ll
const int N = 1e5 + 50;
int n, m;
int r;
int fa[N];
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

vector<pair<int, int>> to[N];
int maxn[N][21];
int maxnn[N][21];
int dep[N];

void dfs(int x, int pre) {
    dep[x] = dep[pre] + 1;
    fa[x] = pre;
    for (auto t : to[x]) {
        int v = t.first;
        if (v == pre) continue;
        int val = t.second;
        maxn[v][0] = val;
        dfs(v, x);
    }
}

int dp[N][21];
int lca(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    int jump = dep[y] - dep[x];
    for (int j = 20; j >= 0; j--) {
        if (jump & (1 << j)) {
            y = dp[y][j];
        }
    }
    if (x == y) return x;
    for (int j = 20; j >= 0; j--) {
        if (dp[x][j] != dp[y][j]) {
            x = dp[x][j];
            y = dp[y][j];
        }
    }
    return fa[x];
}

signed main() {
    cin >> n >> m;
    vector<pair<int, pair<int, int>>> edge, n_edge;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        int u, v, val;
        cin >> u >> v >> val;
        edge.push_back({val, {u, v}});
    }
    sort(edge.begin(), edge.end());
    int ans = 0;
    for (int i = 0; i < edge.size(); i++) {
        int val = edge[i].first;
        int u = edge[i].second.first, v = edge[i].second.second;
        int fx = find(u), fy = find(v);
        if (fx == fy) {
            n_edge.push_back({val, {u, v}});
            continue;
        } else {
            to[u].push_back({v, val});
            to[v].push_back({u, val});
            ans += val;
            fa[fx] = fy;
        }
    }
    r = 1;
    dfs(r, r);
    for (int j = 0; j <= 20; j++) {
        if (j == 0) {
            for (int x = 1; x <= n; x++) {
                dp[x][j] = fa[x];
            }
        } else {
            for (int x = 1; x <= n; x++) {
                dp[x][j] = dp[dp[x][j - 1]][j - 1];
            }
        }
    }
    for (int j = 1; j <= 20; j++) {
        for (int x = 1; x <= n; x++) {
            if (maxn[x][j - 1] == maxn[dp[x][j - 1]][j - 1]) {
                maxn[x][j] = maxn[x][j - 1];
                set<int> s;
                s.insert(maxn[x][j - 1]);
                s.insert(maxnn[x][j - 1]);
                s.insert(maxnn[dp[x][j - 1]][j - 1]);
                if (s.size() >= 2) {
                    auto it = s.rbegin();
                    it++;
                    maxnn[x][j] = *it;
                } else {
                    maxnn[x][j] = 0;
                }
            } else {
                int a = maxn[x][j - 1];
                int b = maxn[dp[x][j - 1]][j - 1];
                maxn[x][j] = max(a, b);
                int candidate1 = min(a, b);
                int candidate2 = max(maxnn[x][j - 1], maxnn[dp[x][j - 1]][j - 1]);
                maxnn[x][j] = max(candidate1, candidate2);
            }
        }
    }
    int ANS = LLONG_MAX;
    for (int i = 0; i < n_edge.size(); i++) {
        int val = n_edge[i].first;
        int u = n_edge[i].second.first, v = n_edge[i].second.second;
        int anc = lca(u, v);
        set<int> sets;
        if (anc == u) {
            int jump = dep[v] - dep[u];
            for (int j = 20; j >= 0; j--) {
                if (jump & (1 << j)) {
                    sets.insert(maxn[v][j]);
                    sets.insert(maxnn[v][j]);
                    v = dp[v][j];
                }
            }
        } else if (anc == v) {
            swap(u, v);
            int jump = dep[v] - dep[u];
            for (int j = 20; j >= 0; j--) {
                if (jump & (1 << j)) {
                    sets.insert(maxn[v][j]);
                    sets.insert(maxnn[v][j]);
                    v = dp[v][j];
                }
            }
        } else {
            int jump = dep[u] - dep[anc];
            for (int j = 20; j >= 0; j--) {
                if (jump & (1 << j)) {
                    sets.insert(maxn[u][j]);
                    sets.insert(maxnn[u][j]);
                    u = dp[u][j];
                }
            }
            jump = dep[v] - dep[anc];
            for (int j = 20; j >= 0; j--) {
                if (jump & (1 << j)) {
                    sets.insert(maxn[v][j]);
                    sets.insert(maxnn[v][j]);
                    v = dp[v][j];
                }
            }
        }
        sets.erase(0); // 移除0的影响
        if (sets.empty()) continue;
        int max_val = *sets.rbegin();
        if (max_val == val) {
            sets.erase(max_val);
            if (sets.empty()) continue;
            max_val = *sets.rbegin();
        }
        if (max_val < val) {
            ANS = min(ANS, ans - max_val + val);
        }
    }
    cout << ANS;
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com