深入探讨严格次小生成树的算法与实现

核心逻辑与数学原理

本章聚焦于最小生成树（MST）在高级竞赛场景下的核心战术变形：严格次小生成树（Strict Second Minimum Spanning Tree）。

1. 严格与非严格的代数界定

设无向连通图 $G=(V, E)$ 的最小生成树为 $T_{ ext{mst}}$，其边权之和为 $W(T_{ ext{mst}})$。次小生成树 $T_{ ext{2nd}}$ 是指在全量生成树集合中，边权和仅次于 $T_{ ext{mst}}$ 的生成树。

• 非严格次小生成树：满足 $W(T_{ ext{2nd}}) \ge W(T_{ ext{mst}})$。
• 严格次小生成树：必须满足 $W(T_{ ext{2nd}}) > W(T_{ ext{mst}})$。

2. 树外边的非树边替换定理（Cycle Property）

次小生成树与最小生成树在拓扑结构上有着极高的重合度。有一个重要的图论定理：必然存在至少一棵次小生成树，它与最小生成树相比，只有一条边不同。

基于此定理，我们的核心战术是路径替换（定理驱动）：

1. 先求解出原图的最小生成树 $T_{ ext{mst}}$。
2. 遍历所有属于 $G$ 但不属于 $T_{ ext{mst}}$ 的非树边 $e = (u, v)$，边权为 $w$。
3. 如果将 $e$ 强行加入 $T_{ ext{mst}}$ 中，树的拓扑结构会被破坏，在 $u$ 到 $v$ 的唯一树上路径上会闭合出一个环路（Cycle）。
4. 为了重新让图收敛为一棵树，必须从 $u$ 到 $v$ 的树上路径中剔除一条边。为了使整体代价上升最少，我们需要剔除该路径上权值最大的边（设为 $max_w$）。
5. 此时新树的代价为 $W_{new} = W(T_{ ext{mst}}) + w - max_w$。

3. 严格次小生成树的“最大与次大”状态设计

若仅求非严格次小生成树，找出路径上的最大边 $max_w$ 即可。但在求解严格次小生成树时，可能会遇到非树边的权值 $w$ 恰好等于树上路径最大边 $max_w$ 的情况。如果此时直接替换，新树总权值不变（$W_{new} = W_{ ext{mst}}$），这就退化为了非严格次小生成树。

为了强制实现 $W_{new} > W_{ ext{mst}}$，当 $w == max_w$ 时，我们不能剔除最大边，而是必须退而求其次，剔除该路径上严格小于 $max_w$ 的次大边（设为 $sec_w$）。因此，我们需要维护树上任意两点路径之间的最大边权与严格次大边权。

算法推导与状态设计

为了在 $O(\log N)$ 的时间复杂度内提取出树上 $u$ 到 $v$ 路径间的最大边与严格次大边，必须借助树上倍增（LCA）技术。

1. 倍增状态定义

定义二维状态矩阵：

• fa[i][k]：节点 $i$ 向上跳跃 $2^k$ 步到达的祖先节点。
• gmax[i][k]：节点 $i$ 向上跳跃 $2^k$ 步的路径上，最大的边权。
• gsec[i][k]：节点 $i$ 向上跳跃 $2^k$ 步的路径上，严格次大的边权（若不存在则标定为 $- ext{inf}$）。

2. 状态转移方程（级联拼凑）

倍增矩阵的初始化通过树上 DFS 完毕后，从 $k = 1$ 开始向高位递推。 设中转节点 $mid = fa[i][k-1]$，则有： fa[i][k] = fa[mid][k-1]

对于最大边和次大边的拼凑，本质是将两段长度为 $2^{k-1}$ 的路径进行合并。由于要提取出严格次大值，需要对四项候选值（两段各自的最大值和次大值）进行归并排序：

$$ ext{gmax}[i][k] = \max(\text{gmax}[i][k-1], \text{gmax}[mid][k-1])$$

次大值的状态转移则需要拦截相同值：

// 伪代码：四值归并提取严格次大
long long vals[4] = { gmax[i][k-1], gmax[mid][k-1], gsec[i][k-1], gsec[mid][k-1] };
sort(vals, vals + 4);
// 从大到小找第一个严格小于 gmax[i][k] 的值作为 gsec[i][k]

C++ 标准源码（严格次小生成树工业级模板）

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 100005;
const int MAXM = 300005;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

struct Edge {
    int u, v;
    long long w;
    bool is_mst;
    bool operator<(const Edge& rhs) const { return w < rhs.w; }
};

struct TreeEdge {
    int to;
    long long weight;
};

Edge edges[MAXM];
std::vector<TreeEdge> tree[MAXN];
int dsu_fa[MAXN];
int depth[MAXN];
int fa[MAXN][18];
long long gmax[MAXN][18];
long long gsec[MAXN][18];

int find_set(int i) {
    if (dsu_fa[i] == i) return i;
    return dsu_fa[i] = find_set(dsu_fa[i]);
}

bool union_set(int i, int j) {
    int root_i = find_set(i), root_j = find_set(j);
    if (root_i != root_j) { dsu_fa[root_i] = root_j; return true; }
    return false;
}

// 树上 DFS 初始化第一层倍增状态
void dfs(int u, int p, int d, long long w_to_p) {
    depth[u] = d;
    fa[u][0] = p;
    gmax[u][0] = w_to_p;
    gsec[u][0] = -INF; // 长度为 1 的路径没有次大边

    for (int k = 1; k < 18; ++k) {
        int mid = fa[u][k-1];
        fa[u][k] = fa[mid][k-1];

        // 归并提取最大与严格次大
        long long candidates[4] = { gmax[u][k-1], gmax[mid][k-1], gsec[u][k-1], gsec[mid][k-1] };
        long long cur_max = std::max(candidates[0], candidates[1]);
        long long cur_sec = -INF;
        for (int i = 0; i < 4; ++i) {
            if (candidates[i] < cur_max) {
                cur_sec = std::max(cur_sec, candidates[i]);
            }
        }
        gmax[u][k] = cur_max;
        gsec[u][k] = cur_sec;
    }

    for (size_t i = 0; i < tree[u].size(); ++i) {
        int v = tree[u][i].to;
        if (v != p) {
            dfs(v, u, d + 1, tree[u][i].weight);
        }
    }
}

// 收集全量路径候选值
void update_candidates(long long u_max, long long u_sec, long long& max_w, long long& sec_w) {
    long long status[4] = { max_w, sec_w, u_max, u_sec };
    long long new_max = std::max({status[0], status[1], status[2], status[3]});
    long long new_sec = -INF;
    for (int i = 0; i < 4; ++i) {
        if (status[i] < new_max) {
            new_sec = std::max(new_sec, status[i]);
        }
    }
    max_w = new_max;
    sec_w = new_sec;
}

// 查询树上 u 到 v 路径的最大与严格次大边
void query_lca(int u, int v, long long& max_w, long long& sec_w) {
    max_w = -INF; sec_w = -INF;
    if (depth[u] < depth[v]) std::swap(u, v);

    for (int k = 17; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            update_candidates(gmax[u][k], gsec[u][k], max_w, sec_w);
            u = fa[u][k];
        }
    }
    if (u == v) return;

    for (int k = 17; k >= 0; --k) {
        if (fa[u][k] != fa[v][k]) {
            update_candidates(gmax[u][k], gsec[u][k], max_w, sec_w);
            update_candidates(gmax[v][k], gsec[v][k], max_w, sec_w);
            u = fa[u][k]; v = fa[v][k];
        }
    }
    update_candidates(gmax[u][0], gsec[u][0], max_w, sec_w);
    update_candidates(gmax[v][0], gsec[v][0], max_w, sec_w);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        std::cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].is_mst = false;
    }

    std::sort(edges, edges + m);
    for (int i = 1; i <= n; ++i) dsu_fa[i] = i;

    long long mst_weight = 0;
    int edges_selected = 0;
    for (int i = 0; i < m; ++i) {
        if (union_set(edges[i].u, edges[i].v)) {
            mst_weight += edges[i].w;
            edges[i].is_mst = true;
            tree[edges[i].u].push_back(TreeEdge{edges[i].v, edges[i].w});
            tree[edges[i].v].push_back(TreeEdge{edges[i].u, edges[i].w});
            if (++edges_selected == n - 1) break;
        }
    }

    // 从 1 号点出发跑 DFS 构建倍增体系
    dfs(1, 0, 1, -INF);

    long long min_delta = INF;
    // 核心遍历：考查每一条非树边
    for (int i = 0; i < m; ++i) {
        if (edges[i].is_mst) continue;

        long long max_w, sec_w;
        query_lca(edges[i].u, edges[i].v, max_w, sec_w);

        // 严格替换逻辑
        if (edges[i].w > max_w) {
            min_delta = std::min(min_delta, edges[i].w - max_w);
        } else if (edges[i].w == max_w && sec_w != -INF) {
            min_delta = std::min(min_delta, edges[i].w - sec_w);
        }
    }

    std::cout << mst_weight + min_delta << "\n";
    return 0;
}

NOIP 实战避坑指南

1. 倍增归并时未排除“等值”，导致严格次小退化： 在倍增合并 gsec[u][k] 时，如果粗暴地写成 gsec[u][k] = max(gsec[u][k-1], gsec[mid][k-1])，由于路径中可能存在多条权值相等的最大边，两段的最大值可能完全相等。这样归并出来的“次大值”在物理上其实仍然是最大值。在后续查询中就会导致 sec_w == max_w。一旦触发非树边与最大边相等的替换分支，计算出来的总权值将不增反降，直接退化为非严格次小生成树。
2. 初始化 gsec 或无解状态时赋错极值： 由于算法要使用 std::max 来提取次大边，因此所有不合法、不存在的次大边状态（比如长度仅为 1 的路径）初始值必须赋予负无穷（如 -INF）。如果图省事将其赋为 0，而图中恰好存在大量边权为负数或者边权为正数的精细数据，max 操作就会误将 0 判定为合法的次大边，从而导致替换差值计算错误。

经典 NOIP/洛谷 真题

1. 洛谷 P4180 [BJWC2010] 严格次小生成树

• 题意描述： 给定一个包含 $N$ 个点、$M$ 条无向边的带权图，求该图的严格次小生成树的边权之和。数据保证存在严格次小生成树。
• 问题本质与核心思路： 这是本章探讨的图论高级战术的完全体真题。核心解题流完全契合上述源码设计：首先利用并查集跑 Kruskal 算法求出 MST，并将树边构建邻接表；然后对树跑一遍 DFS，预处理出 LCA 倍增数组以及维护路径最大与严格次大的二维矩阵；最后枚举所有非树边，通过 LCA 提取出对应树上路径的最大值和次大值，根据严格大于的限制条件分别计算出最小的代价增量（min_delta）。最后将 MST 总权值加上 min_delta 即为最终答案。

2. 洛谷 P2680 [NOIP2015 提高组] 运输计划

• 题意描述： 给出一棵包含 $N$ 个节点的树，树上每条边都有一个运输时间。现在有 $M$ 个运输任务，每个任务都是从节点 $u_i$ 运输到 $v_i$。你可以选择将树上的某一条边的运输时间清零。求清零一条边后，所有运输任务中耗时最长的任务所需时间的最小值。
• 问题本质与核心思路： 虽然这是一道典型的“二分答案 + 树上差分”综合真题，但它在状态提取层面的底层技术与次小生成树完全一致。 题目的核心难点之一在于：当我们二分了一个全局最长耗时上限 $mid$ 后，我们需要找出所有耗时超过 $mid$ 的任务路径的共同交集边。 在实现时，我们需要高效计算每条路径的原始耗时。这就需要预处理出树上任意两点之间的距离。其技术底座就是利用 LCA 倍增。通过维护一个 dist_to_root 数组，结合 $dist(u, v) = dist ext{to ext{root}}[u] + dist ext{to ext{root}}[v] - 2 \cdot dist ext{to ext{root}}[lca(u,v)]$，可在 $O(\log N)$ 时间内快速剥离路径权值。这充分证明了通过倍增技术维护树上路径物理状态是解决 NOIP 级别高级树论、图论问题的标准核心武器。