NeFut Logo NeFut
中 Admin Login

In-depth Exploration of Strict Second Minimum Spanning Tree Algorithms and Implementations

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#algorithm #Tree #LLM

Core Logic and Mathematical Principles

This chapter focuses on the core tactical transformation of Minimum Spanning Tree (MST) in advanced competitive scenarios: Strict Second Minimum Spanning Tree (Strict Second Minimum Spanning Tree).

1. Algebraic Definitions of Strict and Non-Strict

Let the minimum spanning tree of the undirected connected graph $G=(V, E)$ be $T_{ ext{mst}}$, with an edge weight sum of $W(T_{ ext{mst}})$. The second minimum spanning tree $T_{ ext{2nd}}$ refers to the spanning tree with the edge weight sum that is second only to that of $T_{ ext{mst}}$ in the complete set of spanning trees.

2. Non-Tree Edge Replacement Theorem (Cycle Property)

The second minimum spanning tree has a high degree of overlap in topological structure with the minimum spanning tree. There is an important theorem in graph theory: There exists at least one second minimum spanning tree that differs from the minimum spanning tree by only one edge.

Based on this theorem, our core tactic is path replacement (theorem-driven):

  1. First, solve for the minimum spanning tree of the original graph $T_{ ext{mst}}$.
  2. Traverse all non-tree edges $e = (u, v)$ belonging to $G$ but not belonging to $T_{ ext{mst}}$, with edge weight $w$.
  3. If $e$ is forcibly added to $T_{ ext{mst}}$, the topological structure of the tree will be disrupted, resulting in a cycle along the unique path from $u$ to $v$.
  4. To revert the graph back to a tree, one must remove one edge from the path from $u$ to $v$. To minimize the overall cost increase, we need to remove the heaviest edge on that path (denote it as $max_w$).
  5. The cost of the new tree will then be $W_{new} = W(T_{ ext{mst}}) + w - max_w$.

3. Design of "Maximum and Second Maximum" States for Strict Second Minimum Spanning Tree

If we only seek a non-strict second minimum spanning tree, we can simply find the maximum edge $max_w$ on the path. However, when solving for the strict second minimum spanning tree, we may encounter situations where the weight $w$ of a non-tree edge is exactly equal to the maximum edge $max_w$ on the tree path. If we replace it directly, the total weight of the new tree will remain unchanged ($W_{new} = W_{ ext{mst}}$), which degenerates into a non-strict second minimum spanning tree.

To enforce $W_{new} > W_{ ext{mst}}$, when $w == max_w$, we cannot remove the maximum edge; instead, we must settle for the next best option, removing the second largest edge on that path that is strictly less than $max_w$ (denote it as $sec_w$). Therefore, we need to maintain the maximum edge weight and strict second maximum edge weight between any two points on the tree.

Algorithm Derivation and State Design

To extract the maximum and strict second maximum edges between nodes $u$ and $v$ on the tree in $O(\log N)$ time complexity, we must leverage the tree doubling (LCA) technique.

1. Doubling State Definition

Define a two-dimensional state matrix:

2. State Transition Equation (Cascading Merge)

The initialization of the doubling matrix is completed through DFS on the tree, followed by upward propagation starting from $k = 1$. Let the intermediate node be $mid = fa[i][k-1]$, then: fa[i][k] = fa[mid][k-1]

For merging the maximum and second maximum edges, it essentially combines two segments of paths each of length $2^{k-1}$. To extract the strictly second maximum value, we need to perform a merge sort on four candidate values (the maximum and second maximum values of each segment):

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

The transition for the second maximum value needs to intercept equal values:

// Pseudocode: Four-value merge to extract the strictly second maximum
long long vals[4] = { gmax[i][k-1], gmax[mid][k-1], gsec[i][k-1], gsec[mid][k-1] };
sort(vals, vals + 4);
// Find the first value strictly less than gmax[i][k] from largest to smallest as gsec[i][k]

C++ Standard Source Code (Industrial-Grade Template for Strict Second Minimum Spanning Tree)

#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 on the tree to initialize the first level doubling state
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; // There is no second largest edge in a path of length 1

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

        // Merge to extract maximum and strictly second maximum
        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);
        }
    }
}

// Collect all path candidate values
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;
}

// Query the maximum and strictly second maximum edge on the path from u to v on the tree
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;
        }
    }

    // Start DFS from node 1 to construct the doubling system
    dfs(1, 0, 1, -INF);

    long long min_delta = INF;
    // Core traversal: examine each non-tree edge
    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);

        // Strict replacement logic
        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 Practical Pitfall Guide

  1. Failure to Exclude "Equal Values" During Doubling Merge, Leading to Degeneration of Strict Second Minimum: When merging gsec[u][k], if written naively as gsec[u][k] = max(gsec[u][k-1], gsec[mid][k-1]), it is possible that there are multiple maximum edges with equal weights in the path. Thus, the merged "second maximum" may still physically be the maximum. This can lead to sec_w == max_w in subsequent queries. Once a non-tree edge triggers the replacement branch equal to the maximum edge, the calculated total weight will not increase and may decrease, degenerating directly into a non-strict second minimum spanning tree.
  2. Incorrectly Assigning Extreme Values During Initialization of gsec or Invalid States: Since the algorithm uses std::max to extract the second largest edge, all illegal or non-existent second largest edge states (such as paths of length 1) must be initialized to negative infinity (e.g., -INF). If the graph is simplified by assigning it to 0, and there happen to be many edges with negative weights or positive weights in the fine data, the max operation may mistakenly identify 0 as a valid second largest edge, leading to incorrect calculations of replacement differences.

Classic NOIP/Luogu Problems

1. Luogu P4180 [BJWC2010] Strict Second Minimum Spanning Tree

2. Luogu P2680 [NOIP2015 Advanced Group] Transportation Plan

Original Source: local://11.3
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS