严格次小生成树 LCA代码70分求调

/*严格次小生成树
设最小生成树边权为S 
非树边(u,v,w)会与u,v之间的路径行成一个环，设树上u,v之间的最大边权为val1,次大边权为val2
若w>val1 则把val1的那条边替换成(u,v,w)这条边，就得到了严格次小生成树的一个候选答案，边权之和为 S-val1+w
若w=val1 则把val2的那条边替换成(u,v,w)这条边，就得到了严格次小生成树的一个候选答案，边权之和为 S-val2+w
计算出所有候选答案，取最小值即为严格次小生成树
 g[x][k][0]和g[x][k][1]分别表示从x到f[x][k]的路径上的val1和val2
 g[x][k][0]=max(g[x][k-1][0],g[f[x][k-1]][k-1][0])
 if(g[x][k-1][0]==g[f[x][k-1]][k-1][0])
 	g[x][k][1]=max(g[x][k-1][1],g[f[x][k-1]][k-1][1]);
 if(g[x][k-1][0]<g[f[x][k-1]][k-1][0])
 	g[x][k][1]=max(g[x][k-1][0],g[f[x][k-1]][k-1][1]);
 if(g[x][k-1][0]>g[f[x][k-1]][k-1][0])
 	g[x][k][1]=max(g[x][k-1][1],g[f[x][k-1]][k-1][0]);
g[x][0][0]=edge(x,y)
g[x][0][1]=0xcfcfcfcf
*/ 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=N*3;
int n,m,d[N],g[N][22][2],f[N][22];
int head[N],Next[M],ver[M],edge[M],tot=0;
int fa[N],t;
long long ans,anss=0x3f3f3f3f,val1,val2; 
struct node{
	int x,y,z,v;
}e[M];
bool operator<(const node&a,const node&b){
	return a.z<b.z;
}
void add(int x,int y,int z){
	ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void bfs(int root){
	d[root]=0;
	queue<int> q;
	q.push(root);
	while(q.size()){
		int x=q.front(),len=(int)log2(d[x]+1);
		q.pop();
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			if(d[y])
				continue;
			d[y]=d[x]+1;
			f[y][0]=x,g[y][0][0]=edge[i];
			g[y][0][1]=0xcfcfcfcf;
			q.push(y);
			for(int k=1;k<=len;k++){
				f[y][k]=f[f[y][k-1]][k-1];
 				g[y][k][0]=max(g[y][k-1][0],g[f[y][k-1]][k-1][0]);
				if(g[y][k-1][0]==g[f[y][k-1]][k-1][0])
					g[y][k][1]=max(g[y][k-1][1],g[f[y][k-1]][k-1][1]);
				//else
					//g[y][k][1]=min(g[y][k-1][0],g[f[y][k-1]][k-1][0]);				
				if(g[y][k-1][0]<g[f[y][k-1]][k-1][0])
					g[y][k][1]=max(g[y][k-1][0],g[f[y][k-1]][k-1][1]);
				if(g[y][k-1][0]>g[f[y][k-1]][k-1][0])
					g[y][k][1]=max(g[y][k-1][1],g[f[y][k-1]][k-1][0]);
			}
		}
	}
}
int get(int x){
	if(fa[x]==x)
		return x;
	return get(fa[x]);
}
void Kruskal(){
	sort(e+1,e+m+1);
	for(int i=1;i<=m;i++){
		int u=get(e[i].x),v=get(e[i].y),w=e[i].z;
		if(u==v)
			continue;
		e[i].v=1;
		fa[u]=v;
		ans+=w;
		add(e[i].x,e[i].y,w);
		add(e[i].y,e[i].x,w);
	}
}
inline void update(int x,int k){
	int val3=g[x][k][0];
	if(val3>val1)
		val2=val1,val1=val3;
	if(val3>val2&&val3<val1)
		val2=val3;
	val3=g[x][k][1];
	if(val3>val1)
		val2=val1,val1=val3;
	if(val3>val2&&val3<val1)
		val2=val3;
} 
void Lca(int x,int y){
	val1=val2=-0x3f3f3f3f;
	if(d[x]<d[y])
		swap(x,y);
	for(int i=t;i>=0;i--)
		if(d[f[x][i]]>=d[y]){
			update(x,i);
			x=f[x][i];
		}
	if(x==y)
		return ;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i]){
			update(x,i);
			update(y,i);
			x=f[x][i],y=f[y][i];
		}
	update(x,0);
	update(y,0);
}
int main(){
	scanf("%d%d",&n,&m);
	t=(int)log2(n)+1;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[i].x=u,e[i].y=v,e[i].z=w;
	}
	for(int i=1;i<=n;i++)
		fa[i]=i;
	Kruskal();
	bfs(1);
	for(int i=1;i<=m;i++)
		if(!e[i].v){
			int u=e[i].x,v=e[i].y,w=e[i].z;
			Lca(u,v);
			if(val1!=w)
				anss=min(anss,ans-val1+w);
			else
				anss=min(anss,ans-val2+w);	
		} 
	printf("%lld\n",anss);
	return 0;
}