严格次小生成树板子

严格次小生成树：

性质：

1. 边权之和比最小生成树大，比其他生成树小

2. 由最小生成树删除一条树边，加入一条非树边得到

解法：

1. 枚举非树边（u，v)：此时能删除的是（u，v)最小路径上的边

2. 使用倍增法维护最小路径上的最大值和次大值（防止操作后生成树权值和最小生成树权值一样）

const int M =3e5+5;
int n,m;
int f[M];
struct node{int u,v,w;node(){}node(int a,int b,int c){u=a;v=b;w=c;}
};
vector<node>a;
int find(int x){if(f[x]!=x){f[x]=find(f[x]);}return f[x];
}
void merge(int x,int y){if(find(x)!=find(y)){f[find(x)]=find(y);}
}
vector<pii>e[M];
int dep[M];
int vis[M];
int fa[M][30];
int st1[M][30];
int st2[M][30];int ans = inf;
int sum = 0;
void dfs(int u,int Fa,int we){fa[u][0]=Fa;dep[u]=dep[Fa]+1;st1[u][0]=we;st2[u][0]=-inf;for(int j=1;j<=29;j++){fa[u][j]=fa[fa[u][j-1]][j-1];st1[u][j]=max(st1[u][j-1],st1[fa[u][j-1]][j-1]);st2[u][j]=max(st2[u][j-1],st2[fa[u][j-1]][j-1]);if(st1[u][j-1]>st1[fa[u][j-1]][j-1]){st2[u][j]=max(st2[u][j],st1[fa[u][j-1]][j-1]);}else if(st1[u][j-1]<st1[fa[u][j-1]][j-1]){st2[u][j]=max(st2[u][j],st2[u][j-1]);}}for(auto[v,w]:e[u]){if(v==Fa)continue;dfs(v,u,w);}
}
int lca(int u,int v){if(dep[u]<dep[v])swap(u,v);for(int j=29;j>=0;j--){if(dep[fa[u][j]]>=dep[v]){u=fa[u][j];}if(u==v)return u;}for(int j=29;j>=0;j--){if(fa[u][j]!=fa[v][j]){u=fa[u][j];v=fa[v][j];}}return fa[u][0];
}int work(int u,int to,int val){int res= - inf;for(int j = 29 ;j>=0;j--){if(dep[fa[u][j]]>=dep[to]){if(st1[u][j]!=val)res=max(res,st1[u][j]);else res = max(res,st2[u][j]);u=fa[u][j];}}return res;
}void solve(){cin>>n>>m;rep(i,1,n)f[i]=i;rep(i,1,m){int x,b,c;cin>>x>>b>>c;a.pb(node(x,b,c));}sort(a.begin(),a.end(),[](node A,node B){return A.w<B.w;});int id=0;for(auto[u,v,w]:a){if(find(u)==find(v)){id++;continue;}vis[id]=1;merge(u,v);sum+=w;e[u].pb({v,w});e[v].pb({u,w});id++;}dfs(1,0,0);id=0;for(auto[u,v,w]:a){if(vis[id]){id++;continue;}ans=min(ans,sum - work(u, lca(u,v) , w)+w);ans=min(ans,sum - work(v, lca(u,v) , w)+w);id++;}cout<<ans<<endl;
}