93pts求解

#include<iostream>
#include<bitset>
#include<math.h>
#include<algorithm>
using namespace std;
constexpr int N=100000;
int n,m,fa[N],h[N],to[N<<1],w[N<<1],nxt[N<<1],c;
int f[17][N],g[17][N],q[17][N],dep[N],G;
bitset<N+(N<<1)> usd;
long long sum,ans;
struct edge{
	int u,v,w;
}e[N+(N<<1)];
bool cmp(edge e1,edge e2){
	return e1.w<e2.w;
}int dsu(int x){
	if(fa[x]!=x)fa[x]=dsu(fa[x]);
	return fa[x];
}void dfs(int x){
	for(int i=h[x];i!=-1;i=nxt[i]){
		if(to[i]!=f[0][x]){
			g[0][to[i]]=w[i],q[0][to[i]]=-1;
			dep[to[i]]=dep[x]+1,f[0][to[i]]=x,dfs(to[i]);
		}
	}return;
}int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)fa[i]=i,h[i]=-1;
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),e[i].u--,e[i].v--;
	}sort(e,e+m,cmp);
	for(int i=0;i<m;i++){
		if(dsu(e[i].u)!=dsu(e[i].v)){
			to[c]=e[i].v,w[c]=e[i].w,nxt[c]=h[e[i].u],h[e[i].u]=c,c++;
			to[c]=e[i].u,w[c]=e[i].w,nxt[c]=h[e[i].v],h[e[i].v]=c,c++;
			fa[dsu(e[i].u)]=dsu(e[i].v),sum+=e[i].w,usd[i]=1;
		}
	}//cout<<sum<<endl;
   //kruksal
	g[0][0]=-1,q[0][0]=-1,dfs(0),ans=1e15;
	for(int i=1;i<=16;i++){
		for(int j=0;j<n;j++){
			f[i][j]=f[i-1][f[i-1][j]];
			g[i][j]=max(g[i-1][j],g[i-1][f[i-1][j]]);
			q[i][j]=(g[i-1][j]^g[i-1][f[i-1][j]])?
			min(g[i-1][j],g[i-1][f[i-1][j]]):max(q[i-1][j],q[i-1][f[i-1][j]]);
		}
	}for(int i=0;i<m;i++){
		if(usd[i]||e[i].u==e[i].v)continue;
		G=-1;
		if(dep[e[i].u]<dep[e[i].v])e[i].u^=e[i].v,e[i].v^=e[i].u,e[i].u^=e[i].v;
		for(int j=16;j>=0;j--){
			if(dep[f[j][e[i].u]]>=dep[e[i].v]){
				if(e[i].w^g[j][e[i].u])G=max(G,g[j][e[i].u]);
				else G=max(G,q[j][e[i].u]);
				e[i].u=f[j][e[i].u];
			}
		}for(int j=16;j>=0;j--){
			if(f[j][e[i].u]^f[j][e[i].v]){
				if(e[i].w^g[j][e[i].u])G=max(G,g[j][e[i].u]);
				else G=max(G,q[j][e[i].u]);
				e[i].u=f[j][e[i].u];
				if(e[i].w^g[j][e[i].v])G=max(G,g[j][e[i].v]);
				else G=max(G,q[j][e[i].v]);
				e[i].v=f[j][e[i].v];
			}
		}//cout<<e[i].u+1<<' '<<e[i].v+1<<' '<<G<<' '<<Q<<endl;
		//cout<<"jumpt"<<g[0][e[i].u]<<' '<<g[0][e[i].v]<<endl;
		if(e[i].u^e[i].v){
			if(e[i].w^g[0][e[i].u])G=max(G,g[0][e[i].u]);
			else G=max(G,q[0][e[i].u]);
			if(e[i].w^g[0][e[i].v])G=max(G,g[0][e[i].v]);
			else G=max(G,q[0][e[i].v]);
		}if(G>=0)ans=min(ans,sum-G+e[i].w);
//倍增维护最大，次大值。
	}printf("%lld\n",ans);
	return 0;
}