题目链接

<h1>题目描述</h1>

给定一张图，求出它的严格次小生成树。

<h1>解题报告</h1>

预备知识：最小生成树，最近公共祖先

我们首先来考虑一下严格最小生成树和不严格次小生成树的区别。

首先，对于一个图，可能不只有一个最小生成树。

那么，不严格次小生成树，只需要找出不同于该最小生成树中的生成树中权值最小的那一个，同理，这也有可能有多个。

对于严格次小生成树，必须权值要比最小生成树的权值大。当然也有可能有多个。

先考虑不严格次小生成树怎么做。

<h2>不严格次小生成树</h2>

首先，一定有一种非常暴力的算法，能求出最小生成树。显而易见：我们先求出MST，然后每次加入一条边，求一遍MST，取最小值即可。

但是这样来看，时间复杂度非常高，每枚举一条边，就需要跑一遍最小生成树。时间复杂度趋近于$ N^2log_2N $。

这个复杂度我们是不能接受的。

那么，我们来看一下算法二。

我们考虑我们每次在最小生成树中加入一条边，这个最小生成树就会变成一个环。怎么让它成为次小呢？首先，"次"已经做到，因为已经加入了一条新的非原最小生成树的边。然后我们需要做到“小”。不难发现，为了使该树的权值尽量的少，我们需要去除一条最大的非新加入的边。

那么，现在就成功的将这个问题转化到了对于一棵树，快速处理出$ (x,y) $点对的路径中的最大权值。

那么，我们可以通过树上动归或LCA或乱搞等，来在$ N^2 $的时间内来处理（当然更优更好）。由于本人太菜，只会LCA。

那么，恭喜您已经掌握了不严格次小生成树的做法了。

<h2>严格次小生成树</h2>

考虑为什么不严格最小生成树是“不”严格的。

因为它允许权值小于等于的生成树存在。

注意到“等于”，我们不是只需要去掉这个等于就可以了吗？

那么，记录次小值即可。

<h1>代码实现</h1>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

#define LL long long
const int MAXN = 100000 + 5;
const int MAXM = 300000 + 5;
float log2N;

inline void Read(LL &x){
    x = 0ll;char ch = getchar();
    LL flag = 1ll;
    for(;!isdigit(ch);ch = getchar())
        if(ch == '-') flag = -1ll;
    for(;isdigit(ch);ch = getchar())
        x = x * 10 + (ch ^ 48);
    x *= flag;
}

LL N,M,mst;

struct Data{
    LL u,v,w;
    bool inmst;
    bool operator < (const Data &other) const {
        return w < other.w;
    }
}e[MAXM];

struct Node{
    struct Edge *firstEdge;
    LL num,depth;
    bool vis;
}node[MAXN];

struct Edge{
    Node s,t;
    LL w;Edge *next;
}pool[MAXN  2],frog = pool;

Edge New(Node s,Node *t,LL w){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->w = w;ret->next = s->firstEdge;
    return ret;
}

inline void add(LL u,LL v,LL w){
    node[u].firstEdge = New(&node[u],&node[v],w);
    node[v].firstEdge = New(&node[v],&node[u],w);
}

LL fa[MAXN];

LL find(LL x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void Kruskal(){
    std::sort(e + 1,e + M + 1);
    for(LL i = 1;i <= N;i++)
        fa[i] = i;
    LL cnt = 0;
    for(LL i = 1;i <= M;i++){
        LL fu = find(e[i].u),fv = find(e[i].v);
        if(fu == fv) continue;
        fa[fv] = fu;
        e[i].inmst = true;
        mst += e[i].w;
        add(e[i].u,e[i].v,e[i].w);
        if(++cnt == N - 1) break;
    }
}

LL fMAXN,maxMAXN,minMAXN;
//max记录最大值，min记录次大值。

void dfs(Node *v){
    v->vis = true;
    LL now = v->num;
    for(int i = 1;i <= log2N;i++){
        if(v->depth <= (1 << i)) break;
        fnow = ff[now][i-1];
        maxnow = std::max(maxnow,maxf[now][i-1]);
        minnow = std::max(minnow,minf[now][i-1]);
        if(maxnow > maxf[now][i-1])
            minnow = std::max(minnow,maxf[now][i-1]);
        else if(maxnow < maxf[now][i-1])
            minnow = std::max(minnow,maxnow);
    }
    for(Edge *e = v->firstEdge;e;e = e->next){
        if(!e->t->vis){
            e->t->depth = v->depth + 1ll;
            maxe->t->num = e->w;
            mine->t->num = LLONG_MIN;
            fe->t->num = now;
            dfs(e->t);
        }
    }
}

inline LL lca(LL x,LL y){
    LL dx = node[x].depth,dy = node[y].depth;
    if(dx != dy){
        if(dx < dy){
            std::swap(x,y);
            std::swap(dx,dy);
        }
        int d = dx - dy;
        for(int i = 0;i <= log2N;i++){
            if((1 << i) & d) x = fx;
        }
    }
    if(x == y) return x;
    for(int i = log2N;i >= 0;i--){
        if(nodef[x].depth < 0) continue;
        if(fx == fy) continue;
        x = fx;y = fy;
    }
    return fx;
}

inline LL query(LL u,LL v,LL maxx){
    LL ans = LLONG_MIN;
    for(int i = log2N;i >= 0;i--){
        if(nodef[u].depth >= node[v].depth){
            if(maxx != maxu) ans = std::max(ans,maxu);
            else ans = std::max(ans,minu);
            u = fu;
        }
    }
    return ans == LLONG_MIN ? 0 : ans;
}

inline void init(){
    memset(f,-1,sizeof(f));
    for(int i = 1;i <= N;i++){
        node[i].vis = false;
        node[i].depth = 0;
        node[i].num = i;
    }
    log2N = log(N) / log(2) + 1;
    min1 = LLONG_MIN;
    node[1].depth = 1;
}

int main(){
    Read(N);Read(M);
    for(LL i = 1;i <= M;i++){
        Read(e[i].u);Read(e[i].v);Read(e[i].w);
    }
    init();
    Kruskal();
    dfs(&node[1]);
    LL ans = LLONG_MAX;
    for(int i = 1;i <= M;i++){
        if(!e[i].inmst){
            LL lc = lca(e[i].u,e[i].v);
            LL d = e[i].w;
            //DEBUG(lc);DEBUG(d);
            ans = std::min(ans,mst - std::max(query(e[i].u,lc,e[i].w),query(e[i].v,lc,e[i].w)) + e[i].w);
            //DEBUG(ans);
        }
    }
    printf("%lld",ans);
    //getchar();getchar();
    return 0;
}