蒟蒻的代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=3e5+10,INF=0x3f3f3f3f;
int h[N],enter[M*2],ne[M*2],edge[M*2],from[M*2],idx;
int fa[N];
int F[N][15];
int G[N][15][2];//0--最大 1--严格次大
bool is_min[M*2];
int n,m;
int ans,Min;//Min--最小生成树 ans--可能的次小生成树
int depth[N];
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > q;
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
inline void link(int u,int v,int w)
{
    from[idx]=u;
    edge[idx]=w;
    enter[idx]=v;
    ne[idx]=h[u];
    h[u]=idx++;
}
int Kruskal()//计算最小生成树
{
    int res=0,cnt=0;
    while(!q.empty())
    {
        int pos=q.top().second;
        q.pop();
        int u=from[pos],v=enter[pos];
        int x=find(u),y=find(v);
        if(x==y) continue;
        is_min[pos]=is_min[pos^1]=1;//成对变换
        fa[x]=y;
        res+=edge[pos];
        if(++cnt==n-1) return res;
    }
    return INF;
}
inline void dfs(int x,int fa)//将F[]与G[]数组初始化
{
    depth[x]=depth[fa]+1;//深度
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int v=enter[i];
        if( v==fa || !is_min[i] ) continue;//树边
        dfs(v,x);
        F[v][0]=x;
        G[v][0][0]=edge[i];//最大
    }
    for(int k=1;k<=14;k++)
    {
        F[x][k]=F[F[x][k-1]][k-1];
        G[x][k][0]=max(G[x][k-1][0],G[F[x][k-1]][k-1][0]);
        if(G[x][k-1][0]==G[F[x][k-1]][k-1][0]) G[x][k][1]=max(G[x][k-1][1],G[F[x][k-1]][k-1][1]);//严格次大由次大更新
        else if(G[x][k-1][0]>G[F[x][k-1]][k-1][0])  G[x][k][1]=max(G[x][k-1][1],G[F[x][k-1]][k-1][0]);
        else G[x][k][1]=max(G[x][k-1][0],G[F[x][k-1]][k-1][1]);
    }
}
int LCA(int x,int y,int z)
{
    if(depth[x]<depth[y]) swap(x,y);//depth[x]>=depth[y]
    int mx=-INF,mex=-INF;
    for(int k=14;k>=0;k--) 
    {
        if(depth[F[x][k]]>=depth[y]) 
        {
            if(G[x][k][0]<mx) mex=max(mex,G[x][k][0]);
            else mex=max(mx,G[x][k][1]);//mx>mex
            mx=max(mx,G[x][k][0]);
            x=F[x][k];
        }
    }
    if(x==y) 
    {
        if(z>mx) return z-mx;//Min+z-mx
        if(z==mx) return z-mex;//Min+z-mex
        return INF;
    }
    for(int k=14;k>=0;k--) 
    {
        if(F[x][k]!=F[y][k]) 
        {
            if(G[x][k][0]<mx) mex=max(mex,G[x][k][0]);
            else mex=max(mx,G[x][k][1]);
            mx=max(mx,G[x][k][0]);
            if(G[y][k][0]<mx) mex=max(mex,G[y][k][0]);
            else mex=max(mx,G[y][k][1]);
            mx=max(mx,G[y][k][0]);
            x=F[x][k],y=F[y][k];
        }
    }
    return F[x][0];
}
void solve()
{
    ans=INF;
    for(int i=1;i<=m;i++)
    {
        int index=i*2-1;
        if(is_min[index]) continue;
        int u=from[index],v=enter[index],w=edge[index];
        int nw=LCA(u,v,w);
        ans=min(ans,nw+Min);
    }
}
signed main()
{
    memset(h,-1,sizeof h);
    memset(G,-INF,sizeof G);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        link(u,v,w); link(v,u,w);
        q.push({w,i*2-1});
    }
    Min=Kruskal();
    depth[0]=-1;
    dfs(1,0);
    solve();
    printf("%lld",ans);
}