[Luogu P4180][BJWC 2010]严格次小生成树

严格次小生成树，关键是“严格”，如果是不严格的其实只需要枚举每条不在最小生成树的边，如果得到边权和大于等于最小生成树的结束就行。原理就是因为Kruskal非常贪心，只要随便改一条边就能得到一个非严格的次小生成树。然而是严格的QAQ，于是得搞点别的东西来实现“严格”，维护个次大值就行。依次枚举每条边，如果这条边和加上这条边构成的环中最大的边边权相等，取次大值，否则取最大值。

参考代码：

#include<cstdio>
#include<algorithm>
#define ll long long
#include<iostream>
#define A(x) cout << #x << " " << x << endl;
#define qwq 900100
const ll inf = 1000000000000000;
using namespace std;
struct Node 
{
    ll u,v,val,nxt;
    bool used;
} a[2 * qwq],b[2 * qwq];
ll head[qwq];
ll f[qwq];
ll find(ll x) {
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
ll n,m,cnt;
void add(ll u,ll v,ll w) {
    cnt++;
    b[cnt].nxt = head[u];
    head[u] = cnt;
    b[cnt].val = w;
    b[cnt].v = v;
}
bool cmp(Node a,Node b) {
    return a.val < b.val;
}
ll ans = 0ll;
void kruskal() {
    ll k = 0;
    for(ll i = 1; i <= n; i++) f[i] = i;
    for(ll i = 1; i <= m; i++) 
    {
        ll f1 = find(a[i].u);
        ll f2 = find(a[i].v);
        if(f1 != f2) {
            f[f1] = f2;
            k++;
            ans += a[i].val;
            add(a[i].u,a[i].v,a[i].val);
            add(a[i].v,a[i].u,a[i].val);
            a[i].used = 1;
            if(k == n - 1) break;
        }
    }
}
ll fa[qwq][30],dep[qwq];
ll maxx[qwq][30],lmax[qwq][30];
void dfs(ll u,ll pa) {
    fa[u][0] = pa;
    for(int i = head[u]; i; i = b[i].nxt) {
        ll v = b[i].v;
        if(v == pa) continue;
        dep[v] = dep[u] + 1ll;
        maxx[v][0] = b[i].val;
        lmax[v][0] = -inf;
        dfs(v,u);
    }
}
void max_set() {
    for(ll i = 1; i <= 20; i++)
        for(ll u = 1; u <= n; u++) {
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
            maxx[u][i] = max(maxx[u][i - 1],maxx[fa[u][i - 1]][i - 1]);
            lmax[u][i] = max(lmax[u][i - 1],lmax[fa[u][i - 1]][i - 1]);
            if(maxx[u][i - 1] > maxx[fa[u][i - 1]][i - 1])
                lmax[u][i] = max(lmax[u][i],maxx[fa[u][i - 1]][i - 1]);
            else if(maxx[u][i - 1] < maxx[fa[u][i - 1]][i - 1])
                lmax[u][i] = max(lmax[u][i],maxx[u][i - 1]);
        }
}
ll lca(ll x,ll y) {
    if(dep[x] < dep[y]) swap(x,y);
    for(ll i = 20; i >= 0; i--)
        if(dep[fa[x][i]] >= dep[y]) 
            x = fa[x][i];
    if(x == y) return x;
    for(ll i = 20; i >= 0; i--)
        if(fa[x][i] ^ fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    return fa[x][0];
}
ll find_max(ll u,ll v,ll qaq) {
    ll Ans = -inf;
    for(ll i = 20; i >= 0; i--) {
        if(dep[fa[u][i]] >= dep[v]) {
            if(qaq != maxx[u][i])Ans = max(Ans,maxx[u][i]);
            else Ans = max(Ans,lmax[u][i]);
            u = fa[u][i];
        }
    }
    return Ans;
}
int main() 
{
    scanf("%lld %lld",&n,&m);
    for(ll i = 1;i <= m;i++) 
    {
        scanf("%lld %lld %lld",&a[i].u,&a[i].v,&a[i].val);
    }
    sort(a + 1,a + 1 + m,cmp);
    kruskal();
    lmax[1][0] = -inf;
    dep[1] = 1ll;
    dfs(1,-1);
    max_set();
    ll answ = inf;
    for(ll i = 1; i <= m; i++) 
    {
        if(!a[i].used) 
        {
            ll u = a[i].u;
            ll v = a[i].v;
            ll d = a[i].val;
            ll Lca = lca(u,v);
            ll maxu = find_max(u,Lca,d);
            ll maxv = find_max(v,Lca,d);
            answ = min(answ,ans - max(maxu,maxv) + d);
        }
    }
    printf("%lld",answ);
}