[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 = ;

using namespace std;

struct Node

{

    ll u,v,val,nxt;

    bool used;

} a[ * qwq],b[ * 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 = ;

    for(ll i = ; i <= n; i++) f[i] = i;

    for(ll i = ; 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 = ;

            if(k == n - ) break;

        }

    }

}

ll fa[qwq][],dep[qwq];

ll maxx[qwq][],lmax[qwq][];

void dfs(ll u,ll pa) {

    fa[u][] = 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][] = b[i].val;

        lmax[v][] = -inf;

        dfs(v,u);

    }

}

void max_set() {

    for(ll i = ; i <= ; i++)

        for(ll u = ; u <= n; u++) {

            fa[u][i] = fa[fa[u][i - ]][i - ];

            maxx[u][i] = max(maxx[u][i - ],maxx[fa[u][i - ]][i - ]);

            lmax[u][i] = max(lmax[u][i - ],lmax[fa[u][i - ]][i - ]);

            if(maxx[u][i - ] > maxx[fa[u][i - ]][i - ])

                lmax[u][i] = max(lmax[u][i],maxx[fa[u][i - ]][i - ]);

            else if(maxx[u][i - ] < maxx[fa[u][i - ]][i - ])

                lmax[u][i] = max(lmax[u][i],maxx[u][i - ]);

        }

}

ll lca(ll x,ll y) {

    if(dep[x] < dep[y]) swap(x,y);

    for(ll i = ; i >= ; i--)

        if(dep[fa[x][i]] >= dep[y])

            x = fa[x][i];

    if(x == y) return x;

    for(ll i = ; i >= ; i--)

        if(fa[x][i] ^ fa[y][i]) {

            x = fa[x][i];

            y = fa[y][i];

        }

    return fa[x][];

}

ll find_max(ll u,ll v,ll qaq) {

    ll Ans = -inf;

    for(ll i = ; i >= ; 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 = ;i <= m;i++)

    {

        scanf("%lld %lld %lld",&a[i].u,&a[i].v,&a[i].val);

    }

    sort(a + ,a +  + m,cmp);

    kruskal();

    lmax[][] = -inf;

    dep[] = 1ll;

    dfs(,-);

    max_set();

    ll answ = inf;

    for(ll i = ; 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);

}