倍增无耻求助

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define int long long

using namespace std;

struct edge2{
	int u,v,w;
	bool operator <(edge2 a) const{
		return w<a.w;
	}
}a[300002];

struct edge{
	int v,w;
};

int n,m,ans=0x7fffffff,tot;
vector<edge> g[200002];
bool b[200002];
int dep[200002],fa[200002][30],w[200002][30],f[200002];

void dfs(int);
int lca(int,int,int);
int kruskal();
int find(int);

signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>a[i].u>>a[i].v>>a[i].w;
	}
	tot=kruskal();
	dfs(1);
	for(int i=1;i<=n;++i){
		if(!b[i]){
			if(a[i].w!=lca(a[i].u,a[i].v,a[i].w))
				ans=min(ans,tot+a[i].w-lca(a[i].u,a[i].v,a[i].w));
		}
	}
	cout<<ans<<endl;
}

int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}

int kruskal(){
	int tot=0;
	sort(a+1,a+m+1);
	for(int i=1;i<=n;++i)
		f[i]=i;
	for(int i=1;i<=m;++i){
		if(find(a[i].u)!=find(a[i].v)){
			b[i]=1;
			f[find(a[i].u)]=find(a[i].v);
			tot+=a[i].w;
			g[a[i].u].push_back({a[i].v,a[i].w});
			g[a[i].v].push_back({a[i].u,a[i].w});
		}
	}
	return tot;
}

void dfs(int u){
	for(int i=1;i<=log2(n);++i){
		fa[u][i]=fa[fa[u][i-1]][i-1];
		w[u][i]=max(w[fa[u][i-1]][i-1],w[u][i-1]);
	}
	for(auto &vn:g[u]){
		int v=vn.v,ww=vn.w;
		if(v!=fa[u][0]){
			fa[v][0]=u;
			w[v][0]=ww;
			dep[v]=dep[u]+1;
			dfs(v);
		}
	}
}

int lca(int a,int b,int c){
	int ans=-1;
	if(dep[a]>dep[b])
		swap(a,b);
	int cha=dep[b]-dep[a];
	for(int i=0;cha;++i){
		if(cha&1){
			if(w[b][i]<c)
				ans=max(ans,w[b][i]);
			b=fa[b][i];
		}
		cha>>=1;
	}
	if(a==b)
		return ans!=-1?ans:c;
	for(int i=log2(n);i>=0;--i){
		if(fa[a][i]!=fa[b][i]){
			if(w[a][i]<c)
				ans=max(ans,w[a][i]);
			if(w[b][i]<c)
				ans=max(ans,w[b][i]);
			a=fa[a][i],b=fa[b][i];
		}
	}
	if(w[a][0]<c)
		ans=max(ans,w[a][0]);
	if(w[b][0]<c)
		ans=max(ans,w[b][0]);
	return ans!=-1?ans:c;
}