按秩合并并查集，WA on #016,#020,#28

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int n,q,a[maxn],b[maxn],fa[maxn],sz[maxn],ans[maxn],cnt;
ll d[maxn],dis[maxn];
bool vis[maxn];
int gf(int x){return (fa[x]==x ? x : fa[x]=gf(fa[x]));}
vector <int> e[maxn];
void dfs(int now,int pre,ll k){
	dis[now]+=k;
	for(int i:e[now]) if(i!=pre) dfs(i,now,k);
}signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q ;
	memset(dis,127,sizeof(dis));
	for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
	for(int i=1;i<=q;i++) cin >> a[i] >> b[i] >> d[i] ;
	for(int i=1;i<=q;i++){
		if(a[i]==b[i] && d[i]) continue;
		if(!vis[a[i]] && !vis[b[i]]){
			ans[++cnt]=i;
			dis[a[i]]=0,dis[b[i]]=d[i];
			vis[a[i]]=1;
			vis[b[i]]=1;
			fa[b[i]]=a[i],sz[a[i]]++;
			e[a[i]].push_back(b[i]);
		}else if(vis[a[i]] && !vis[b[i]]){
			ans[++cnt]=i;
			dis[b[i]]=dis[a[i]]+d[i];
			vis[b[i]]=1;
			int x=gf(a[i]);
			fa[b[i]]=x,sz[x]++;
			e[x].push_back(b[i]);
		}else if(!vis[a[i]] && vis[b[i]]){
			ans[++cnt]=i;
			dis[a[i]]=dis[b[i]]-d[i];
			vis[a[i]]=1;
			int x=gf(b[i]);
			fa[a[i]]=x,sz[x]++;
			e[x].push_back(a[i]);
		}else if(vis[a[i]] && vis[b[i]]){
			int x=gf(a[i]),y=gf(b[i]);
			if(x==y){
				if(dis[b[i]]-dis[a[i]]==d[i]) ans[++cnt]=i;
			}else{
				if(sz[x]<sz[y]) swap(x,y),swap(a[i],b[i]),d[i]=-d[i];
				dfs(y,0,dis[a[i]]+d[i]-dis[b[i]]);
				ans[++cnt]=i;
				fa[y]=x,sz[x]+=sz[y];
				e[x].push_back(y);
			} 
		}
	}for(int i=1;i<=cnt;i++) cout << ans[i] << " " ;
	return 0;
}