来一个不用 HLD / LCT 的做法。其实没有什么本质上的差别
首先容易想到离线，并且满足条件的图一定是边仙人掌，我们把离线后得到的图缩点，形成一片森林，并且标记树边。树边显然必选，主要来看非树边。
维护 $pre(x)$ 表示从根到 $x$ 的边权异或和，设当前我们考虑的非树边是 $(x,y)$，那么如果 $x,y$ 已经处于同一个环里或者 $pre(x)\oplus pre(y)\oplus w(x,y)\neq1$ 是不行的，否则就可以加进去。
然后怎么实现查找是否在同一个环里之类的就用 time-stamp & BIT 解决。
#include<bits/stdc++.h>
using namespace std;
const int N=300100,M=500100;
int n,m,ix[M],iy[M],iw[M],sjc,fa[20][N],indfn[N],outdfn[N],tag[M],dep[N],pre[N];
vector<pair<int,int>> G[N];
void dfs(int x,int las)
{
fa[0][x]=las;
indfn[x]=++sjc;
dep[x]=dep[las]+1;
for(int i=1; i<20; ++i) fa[i][x]=fa[i-1][fa[i-1][x]];
for(auto [y,w]:G[x]) if(y!=las) pre[y]=pre[x]^w,dfs(y,x);
outdfn[x]=sjc;
}
int fwk[N];
void ins(int x,int y) { for(; x<=n; x+=x&-x) fwk[x]+=y; }
int find(int x)
{
int res=0;
for(; x; x-=x&-x) res+=fwk[x];
return res;
}
int lh[N];
int dsuFind(int x)
{
while(x!=lh[x]) x=lh[x]=lh[lh[x]];
return x;
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19; ~i; --i) if(dep[fa[i][x]]>=dep[y]) x=fa[i][x];
if(x==y) return x;
for(int i=19; ~i; --i) if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
iota(lh+1,lh+n+1,1);
for(int i=1; i<=m; ++i)
{
cin>>ix[i]>>iy[i]>>iw[i];
int x=dsuFind(ix[i]),y=dsuFind(iy[i]);
if(x!=y)
{
G[ix[i]].emplace_back(iy[i],iw[i]);
G[iy[i]].emplace_back(ix[i],iw[i]);
tag[i]=1,lh[x]=y;
}
}
for(int i=1; i<=n; ++i) if(!dep[i]) dfs(i,0);
for(int i=1; i<=m; ++i)
{
if(tag[i]) cout<<"YES\n";
else
{
int x=ix[i],y=iy[i];
if(find(indfn[x])+find(indfn[y])-find(indfn[LCA(x,y)])*2>0||(pre[x]^pre[y]^iw[i])!=1) cout<<"NO\n";
else
{
cout<<"YES\n";
while(x!=y) (dep[x]<dep[y])&&(x^=y^=x^=y),ins(indfn[x],1),ins(outdfn[x]+1,-1),x=fa[0][x];
}
}
}
return 0;
}