玄关求问

#include<bits/stdc++.h>

using namespace std;
const int N=2e6+10,M=5e5+10;
int n,m,x,y,z,fat[N],fa[N],f[N][20],q,dep[N],mx[N][20],fa_len[N],cnt,sfa[N],zx[N];
bool mark[N];
struct edge{int x,y,z,id;}a[N],b[N];
bool _cmp(edge a,edge b){return a.z <b.z;}
int getfa(int x){return x==fat[x]?x:fat[x]=getfa(fat[x]);}
void mix(int x,int y){fat[x]=y;}
vector<int>now_g[M];
vector<int>g[M];
vector<int>_long[M];
void build(int x){
	mark[x]=true;
	mx[x][0]=a[fa_len[x]].z;
	f[x][0]=fa[x];
	for(int i=1;i<=19;i++)f[x][i]=f[f[x][i-1]][i-1],mx[x][i]=max(mx[f[x][i-1]][i-1],mx[x][i-1]);
	for(int i=0;i<now_g[x].size();i++){
		if(mark[now_g[x][i]])continue;
		g[x].push_back(now_g[x][i]);
		fa[now_g[x][i]]=sfa[now_g[x][i]]=x;
		dep[now_g[x][i]]=dep[x]+1;
		fa_len[now_g[x][i]]=_long[x][i];
		build(now_g[x][i]);
	}
}
int LCA(int x,int y){
	int ans=0x3f3f3f3f;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[f[x][i]]>=dep[y])ans=min(ans,mx[x][i]),x=f[x][i];
	if(x==y)return ans;
	for(int i=19;i>=0;i--)
		if(f[x][i]!=f[y][i]){
			ans=min(ans,min(mx[x][i],mx[y][i]));
			x=f[x][i];
			y=f[y][i];
		}
	return min(ans,min(mx[x][0],mx[y][0]));
}
int main(){
	dep[1]=1;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)fat[i]=i,sfa[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		a[i]={(edge){x,y,z,i}};
	}sort(a+1,a+m+1,_cmp);
	for(int i=1;i<=m;i++){
		int aa=getfa(a[i].x),bb=getfa(a[i].y);
		if(aa!=bb){
			mix(aa,bb);
			now_g[a[i].x].push_back(a[i].y);
			now_g[a[i].y].push_back(a[i].x);
			_long[a[i].x].push_back(a[i].id);
			_long[a[i].y].push_back(a[i].id);
		}
		else b[++cnt]=a[i];
	}
	build(1);
	sort(b+1,b+cnt+1);
	for(int i=1;i<=cnt;i++){
		x=b[i].x ,y=b[i].y ,z=b[i].z ;
		int s=LCA(x,y);
		while(x!=s){
			zx[fa_len[x]]=z;
			x=sfa[x];
		}sfa[b[i].x ]=s;
		while(y!=s){
			zx[fa_len[y]]=z;
			y=sfa[y];
		}sfa[b[i].y ]=s;
	}
	return 0;
}