严格次小生成树

如果我早点遇见你，结局是不是会不一样

模板题链接

很久没有写过这么长的代码了
重要部分就是对倍增 LCA 的改动

以下是代码，维护了最大边权和次大边权

// Created by qyy on 2024/6/4.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define PII pair<int, int>
#define endl "\n"

const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
#define int long long

int n, m, f[N];

int ekcnt = 0;
struct Edge_Kru{
    int from, to;
    ll val;
    bool flag;
}ek[N];

int head[N], cnt;
struct Edge{
    int from, to, nxt;
    ll val;
}e[N];
void add(int u, int v, ll val){
    e[++cnt].from = u;
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    e[cnt].val = val;
    head[u] = cnt;
}

bool cmp(Edge_Kru a, Edge_Kru b){
    return a.val < b.val;
}

int find_set(int x){
    if(f[x] != x) f[x] = find_set(f[x]);
    return f[x];
}
void merge_set(int x, int y){
    int fx = find_set(x), fy = find_set(y);
    if(fx != fy) f[fx] = fy;
}

ll dp[N][20], dp2[N][20]; // 分别是最大边权与次大边权

int fa[N][20], deep[N];
void dfs(int x, int father){
    deep[x] = deep[father] + 1;
    fa[x][0] = father;
    for(int i = 1; (1 << i) <= deep[x]; i++){
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
        dp[x][i] = max(dp[x][i - 1], dp[fa[x][i - 1]][i - 1]);
        dp2[x][i] = max(dp2[x][i - 1], dp2[fa[x][i - 1]][i - 1]);
        if(dp[x][i] > dp[x][i - 1]) dp2[x][i] = max(dp2[x][i], dp[x][i - 1]);
        if(dp[x][i] > dp[fa[x][i - 1]][i - 1]) dp2[x][i] = max(dp2[x][i], dp[fa[x][i]][i - 1]);
    }

    for(int i = head[x]; i != 0; i = e[i].nxt){
        int v = e[i].to;
        if(v != father)
        {
            dp[v][0] = e[i].val;
            // 问题是 次大的该怎么维护呢。
            dp2[v][0] =  0;
            dfs(v, x);
        }
    }
}

// LCA 也得改，直接修改为查询函数
ll LCA(int x, int y, ll val){
    if(deep[x] < deep[y]) swap(x, y);
    // 目的找到第一个小于 val 的最大值
    ll ans = 0;
    for(int i = 19; i >= 0; i--)
        if(deep[x] - (1 << i) >= deep[y]){

            if(dp[x][i] == val){
                ans = max(ans, dp2[x][i]);
            }else{
                ans = max(ans, dp[x][i]);
            }
            x = fa[x][i];
        }

    if(x == y) return ans;
    // x 和 y 一起向上跳
    for(int i = 19; i >= 0; i--){
        if(fa[x][i] != fa[y][i]){
            if(dp[x][i] == val){
                ans = max(ans, dp2[x][i]);
            }else{
                ans = max(ans, dp[x][i]);
            }
            if(dp[y][i] == val){
                ans = max(ans, dp2[y][i]);
            }else{
                ans = max(ans, dp[y][i]);
            }

            x = fa[x][i];
            y = fa[y][i];
        }
    }
    if(dp[x][0] == val){
        ans = max(ans, dp2[x][0]);
    }else{
        ans = max(ans, dp[x][0]);
    }
    if(dp[y][0] == val){
        ans = max(ans, dp2[y][0]);
    }else{
        ans = max(ans, dp[y][0]);
    }
    return ans;
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        f[i] = i;
    }
    for(int i = 1; i <= m; i++){
        int u, v;
        ll val;
        cin >> u >> v >> val;
        if(u != v)
            ek[++ekcnt] = {u, v, val, false};
    }
    ll ans = 0;
    int begid = 0;
    sort(ek + 1, ek + 1 + ekcnt, cmp);
    for(int i = 1; i <= ekcnt; i++){
        int u = ek[i].from, v = ek[i].to;
        ll val = ek[i].val;
        int fu = find_set(u), fv = find_set(v);
        if(fu != fv){
            ek[i].flag = true;
            merge_set(u, v);
            add(u, v, val);
            add(v, u, val);
            begid = i + 1;
            ans += val;
        }
    }
    // 建树建完了
    dfs(1, 0);

    ll ans2 = inf;
    for(int i = 1; i <= ekcnt; i++){
        if(ek[i].flag) continue;
        int u = ek[i].from, v = ek[i].to;
        if(u == v) continue;
        ll val = ek[i].val;
        ans2 = min(ans2, val - LCA(u, v, val));
    }
    cout << ans + ans2 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

我应该再也获得不了这样的机会了