求大佬指点

LCA

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int M=300010;
const int N=100010;
typedef long long ll;
struct sd{
	int from;
	int to;
	ll value;
}a[M];
int n,m;
int p[N],fa[N];bool flag[M];
vector<int>edge[M];
int shen[N];bool vs[N];
int G[N][35][2];
int F[N][35];
inline int get(){
	char c;
	int sign=1;
	while((c=getchar())<'0'||c>'9') if(c=='-') sign=-1;
	int res=c-'0';
	while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	return res*sign;
}
int cmp(const sd &A,const sd &B){
	if(A.value<B.value) return 1;
	else return 0;
}
int findth(int x)
{
	if(p[x]==x)
		return x;
	else
		return p[x]=findth(p[x]);
}
void unionn(int x,int y)
{
	int x1=findth(x);
	int y1=findth(y);
	if(x1!=y1)
	p[x1]=y1;
}
void dfs(int x){
	vs[x]=true;
	for(int i=1;i<=30;i++){
		F[x][i]=F[F[x][i-1]][i-1];
		G[x][i][0]=max(G[x][i-1][0],G[F[x][i-1]][i-1][0]);
		if(G[x][i-1][0]==G[F[x][i-1]][i-1][0])
			G[x][i][1]=max(G[x][i-1][1],G[F[x][i-1]][i-1][1]);
		else if(G[x][i-1][0]<G[F[x][i-1]][i-1][0])
			G[x][i][1]=max(G[x][i-1][0],G[F[x][i-1]][i-1][1]);
		else
			G[x][i][1]=max(G[x][i-1][1],G[F[x][i-1]][i-1][0]);
	}
	for(int i=0;i<edge[x].size();i++){
		int y=a[edge[x][i]].to+a[edge[x][i]].from-x;
		if(vs[y]) continue;
		shen[y]=shen[x]+1;
		F[y][0]=x;
		G[y][0][0]=a[edge[x][i]].value;
		G[y][0][1]=-1e9;
		dfs(y);
	}
}
int lca(int x,int y){
	if(shen[x]<shen[y]) swap(x,y);
	if(shen[x]!=shen[y]){
		for(int i=30;i>=0;i--){
			int ju=shen[x]-shen[y];
			if(ju&(1<<i)){
				x=F[x][i];
			}
		}
	}
	if(x==y) return x;
	for(int i=30;i>=0;i--){
		if(F[x][i]!=F[y][i]){
			x=F[x][i];
			y=F[y][i];
		}
	}
	return F[x][0];
}
int work(int x,int y,int z){
	if(x==y) return 0;
	int LCA=lca(x,y);
	int Max=0,Cimax=0;
	for(int i=30;i>=0;i--){
		int xju=shen[x]-shen[LCA];
		int yju=shen[y]-shen[LCA];
		if(xju&(1<<i)){
			int lin1=G[x][i][0];
			int lin2=G[x][i][1];
			if(lin1>Max){Cimax=Max;Max=lin1;}
			if(lin1<Max&&lin1>Cimax) Cimax=lin1;
			if(lin2>Cimax&&lin2<Max) Cimax=lin2;
			x=F[x][i];
		}
		if(yju&(1<<i)){
			int lin1=G[y][i][0];
			int lin2=G[y][i][1];
			if(lin1>Max){Cimax=Max;Max=lin1;}
			if(lin1<Max&&lin1>Cimax) Cimax=lin1;
			if(lin2>Cimax&&lin2<Max) Cimax=lin2;
			y=F[y][i];
		}
	}
	if(Max==z) return z-Cimax;
	else return z-Max;
}
int main()
{
	n=get();m=get();
	for(int i=1;i<=m;i++){
		int x,y;ll z;
		x=get();y=get();z=get();
		a[i].from=x;a[i].to=y;a[i].value=z;
	}
	sort(a+1,a+m+1,cmp);
	ll ans=0;
	ll mxrede=-1;
	int ls=n-1;
	for(int i=1;i<=n;i++)
		p[i]=i;
	for(int i=1;i<=m&&ls;i++){
		if(findth(a[i].from)!=findth(a[i].to)){
			flag[i]=true;
			ans+=a[i].value;
			unionn(a[i].to,a[i].from);
			mxrede=max(mxrede,a[i].value);
			ls--;
		}
	}
	for(int i=1;i<=m;i++){
		if(flag[i]){
			edge[a[i].from].push_back(i);
			edge[a[i].to].push_back(i);
		}
	}
	shen[1]=1;
	dfs(1);
	int res=2147483647;
	for(int i=1;i<=m;i++){
		if(!flag[i]){
			if(a[i].value-mxrede>res) break;
			int lin=work(a[i].from,a[i].to,a[i].value);
			res=min(res,lin);
			if(res==0) res=1e9;
		}
	}
	printf("%lld\n",ans+(res==1e9?0:res));
	return 0;
}