已经被这道题卡了四天了。。。

在 codeforces 交wa 第7个点

#include<bits/stdc++.h>
 
using namespace std;
#define endl '\n'
#define push_back emplace_back
#define int long long
constexpr int N=2e5+5,M=2e5+5;
 
int n,m,x,y,z;
int fat[N],fa[N],f[N][22],dep[N],mx[N][22],lg[N];
int fa_len[N],sfa[N],zx[N];
int ans[N],tot,cnt;
bitset<N> mark;
 
struct edge {
	int x,y,z,id;
} a[N],b[N],c[N],ya[N];
 
bool _cmp1(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]=lg[fa_len[x]];
	f[x][0]=sfa[x];
	for(int i=1; i<=21; 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;
		//	cout<<ya[_long[x][i]].x <<" "<<ya[_long[x][i]].y <<" "<<ya[_long[x][i]].z<<endl;
		g[x].push_back(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_or_ST(int x,int y,bool wa) {
	int ans=0;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=21; i>=0; i--)
		if(dep[f[x][i]]>=dep[y])ans=max(ans,mx[x][i]),x=f[x][i];
	if(x==y)return wa?ans:x;
	for(int i=21; i>=0; i--)
		if(f[x][i]!=f[y][i]) {
			ans=max(ans,max(mx[x][i],mx[y][i]));
			x=f[x][i];
			y=f[y][i];
		}
	return wa?max(ans,max(mx[x][0],mx[y][0])):f[x][0];
}
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
//freopen("IN.in","r",stdin);
	memset(ans,0x3f,sizeof(ans));
	dep[1]=1;
	cin>>n>>m;
	for(int i=1; i<=n; i++)fat[i]=sfa[i]=i;
	for(int i=1; i<=m; i++) {
		cin>>x>>y>>z;
		ya[i]=a[i]=(edge) {
			x,y,z,i
		};
	}
	sort(a+1,a+m+1,_cmp1);
	for(int i=1; i<=m; i++) {
		lg[a[i].id]=a[i].z;
		x=getfa(a[i].x),y=getfa(a[i].y);
		if(x!=y) {
			c[++tot]=a[i];
			mix(x,y);
			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,_cmp1);
	for(int i=1; i<=cnt; i++) {
		x=b[i].x ,y=b[i].y ,z=b[i].z ;
		int s=LCA_or_ST(x,y,0);
		while(dep[x]>dep[s]) {
			ans[fa_len[x]]=min(ans[fa_len[x]],z-1);
			int yy=x;
			x=sfa[x];
			sfa[yy]=s;
		}
		sfa[b[i].x ]=s;
		while(dep[y]>dep[s]) {
			ans[fa_len[y]]=min(ans[fa_len[y]],z-1);
			int yy=y;
			y=sfa[y];
			sfa[yy]=s;
		}
		sfa[b[i].y ]=s;
		ans[b[i].id ]=LCA_or_ST(b[i].x ,b[i].y ,1)-1;
	}
	int qe=m;
	//io.read(qe);
	for(int i=1; i<=qe; i++) {
		//	io.read(x);
		x=i;
		if(ans[x]>=0x3f3f3f3f)ans[x]=-1;
		cout<<ans[x]<<endl;
	}
	return 0;
}
*/