rt 找不出错误了 求巨佬帮看一下 提交记录

做法:kruscal+倍增lca

代码：

#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define inf 2000000005
using namespace std;
inline int read()
{
	int x=0; char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x;
}

int n,m;
struct A{
	int t,d;
};
vector<A>e[N];
int fa[N][20],dep[N],lg[N];
ll g[N][22][20];
ll sum,ans=1e15;
struct edge{
	int x,y,d;
	bool operator < (const edge &a)const{
		return d<a.d;
	}
	bool f;
}ed[N*3];

inline int find(int x)
{
	return x==fa[x][0]?x:fa[x][0]=find(fa[x][0]);	
} 

inline void kru()
{
	sort(ed+1,ed+1+m);
	for(int i=1;i<=n;++i) fa[i][0]=i;
	int cnt=0,j=1,x,y,fx,fy;
	while(cnt<n-1){
		x=ed[j].x,y=ed[j].y;
		fx=find(ed[j].x),fy=find(ed[j].y);
		if(fx==fy) {
			++j;
			continue;
		}
		e[x].push_back(A{y,ed[j].d});
		e[y].push_back(A{x,ed[j].d});
		fa[fx][0]=fy;
		sum+=ed[j].d,ed[j].f=1;
		++cnt,++j;
	}
}

inline void dfs(int x,int fath)
{
	fa[x][0]=fath,dep[x]=dep[fath]+1;
	g[x][0][1]=-inf;
	for(int i=1;i<lg[dep[x]];++i){
		fa[x][i]=fa[fa[x][i-1]][i-1],
		g[x][i][0]=max(g[x][i-1][0],g[fa[x][i-1]][i-1][0]);
		if(g[x][i-1][0]==g[fa[x][i-1]][i-1][0])
			g[x][i][1]=max(g[x][i-1][0],g[fa[x][i-1]][i-1][0]);
		else if(g[x][i-1][0]<g[fa[x][i-1]][i-1][0])
			g[x][i][1]=max(g[x][i-1][0],g[fa[x][i-1]][i-1][1]);
		else
			g[x][i][1]=max(g[x][i-1][1],g[fa[x][i-1]][i-1][0]);
	}
	for(int i=0;i<e[x].size();++i){
		int t=e[x][i].t;
		if(t==fath) continue;
		g[t][0][0]=e[x][i].d;
		dfs(t,x);
	}
}

inline void query(int x,int y,ll &x0,ll &x1)
{
	x0=0,x1=-inf;
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]){
		int up=lg[dep[x]-dep[y]]-1;
		if(g[x][up][0]>x0){
			if(x0>x1) x1=x0;
			x0=g[x][up][0];	
		}else x1=max(x1,g[x][up][0]);
		x1=max(x1,g[x][up][1]);
		x=fa[x][up];
	}
	if(x==y) return;
	for(int i=19;i>=0;--i)
		if(fa[x][i]!=fa[y][i]){
			if(g[x][i][0]>x0){
				if(x0>x1) x1=x0;
				x0=g[x][i][0];
			}else x1=g[x][i][0];
			if(g[y][i][0]>x0){
				if(x0>x1) x1=x0;
				x0=g[y][i][0];
			}else x1=g[y][i][0];
			x1=max(x1,g[x][i][1]),x1=max(x1,g[y][i][1]);;
			x=fa[x][i],y=fa[y][i];
		}
	if(g[x][0][0]>x0){
		if(x0>x1) x1=x0;
		x0=g[x][0][0];
	}else x1=max(x1,g[x][0][0]);
	if(g[y][0][0]>x0){
		if(x0>x1) x1=x0;
		x0=g[y][0][0];
	}else x1=max(x1,g[y][0][0]);
	x1=max(x1,g[x][0][1]);
	x1=max(x1,g[y][0][1]);
	return;
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;++i)
		ed[i].x=read(),ed[i].y=read(),ed[i].d=read();
	kru();
	//cout<<sum<<endl;
	for(int i=1;i<=n;++i)
		lg[i]=lg[i-1]+((1<<lg[i-1])==i);
	dep[0]=-1;
	dfs(1,0);
	/*for(int i=1;i<=n;++i){
		printf("%d %d:\n",i,g[i][0][0]);
		for(int j=1;j<lg[dep[i]];++j) printf("%d ",g[i][j][1]);
		printf("\n");
	}*/
	ll val1,val2;
	for(int i=1;i<=m;++i){
		if(ed[i].f) continue;
		query(ed[i].x,ed[i].y,val1,val2);
		//printf("%d %d %d %d %d\n",ed[i].x,ed[i].y,ed[i].d,val1,val2);
		if(val1==ed[i].d)
			ans=min(ans,sum+ed[i].d-val2);
		else
			ans=min(ans,sum+ed[i].d-val1);
	}
	cout<<ans;
	return 0;
}
```