49求条

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=3e5+10;
int n,m,f[N][20],d[N],d1[N][20],mst,d2[N][20],p[N];
struct node{
	int u,v,w,flag;
}a[M];
vector<pair<int,int>> g[N];
bool cmp(struct node a,struct node b){
	return a.w<b.w;
}
int find(int x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}
void kkk(){
	sort(a+1,a+1+m,cmp);
	mst=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	for(int i=1;i<=m;i++){
		int u=a[i].u,v=a[i].v,w=a[i].w;
		u=find(u),v=find(v);
		if(u!=v){
			g[u].push_back({v,w});
			g[v].push_back({u,w});
			p[u]=v;
			cnt++;
			mst+=w;
			a[i].flag=1;
			if(cnt==n-1) break;
		}
	}
}
void dfs(int u,int fa,int dep){
	d[u]=dep,f[u][0]=fa;
	for(int i=1;i<20;i++){
		f[u][i]=f[f[u][i-1]][i-1];
		d1[u][i]=max(d1[u][i-1],d1[f[u][i-1]][i-1]);
		if(d1[u][i-1]==d1[f[u][i-1]][i-1])
		d2[u][i]=max(d2[u][i-1],d2[f[u][i-1]][i-1]);
	else{
		d2[u][i]=min(d1[u][i-1],d1[f[u][i-1]][i-1]);
		d2[u][i]=max(d2[u][i],max(d2[u][i-1],d2[f[u][i-1]][i-1]));
	}
}
	for(auto t:g[u]){
		int v=t.first;
		int w=t.second;
		if(v==fa) continue;
		d1[v][0]=w,d2[v][0]=0;
		dfs(v,u,dep+1);
	}
}
int lca(int x,int y){
	if(d[x]<d[y]) swap(x,y);
	for(int i=19;i>=0;i--){
		if(d[f[x][i]]>=d[y]){
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i],y=f[y][i];
		}
	}
	return f[x][0];
}
void update(int u,int t,int &m1,int &m2){
	for(int i=19;i>=0;i--){
		if(d[f[u][i]]>=d[t]){
			if(d1[u][i]>m1){
				m2=max(m1,d2[u][i]);
				m1=d1[u][i];
			}
			else if(d1[u][i]<m1&&d1[u][i]>m2){
				m2=d1[u][i];
			}
			u=f[u][i];
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].u>>a[i].v>>a[i].w;
	}
	kkk();
	dfs(1,0,1);
	int ans=2e9;
	for(int i=1;i<=m;i++){
		if(!a[i].flag){
			int u=a[i].u,v=a[i].v,w=a[i].w;
			int t=lca(u,v);
			int m1=0,m2=0;
			update(u,t,m1,m2);
			update(v,t,m1,m2);
			if(w==m1) ans=min(ans,mst+w-m2);
			else ans=min(ans,mst+w-m1);
		}
	}
	cout<<ans<<"\n";
	return 0;
}