称权值异或和为 的简单环为合法的环。
假设两个合法的环有至少一条公共边,那么考虑它们组成的大环的权值:每条公共边上的权值相同可以抵消,其他边上的权值异或和相同,也抵消,则大环的权值为 ——显然这两个环组成的大环不是合法的,所以原图一定是一个仙人掌状物。
然后考虑仙人掌是个什么样的东西:对它建出 DFS 树,每条非树边连接的两个点 在树上所形成的链 互不相交。那么把询问离线,用并查集维护,先建出这棵 DFS 树,然后对于每条非树边判断是否合法。具体来说,判断:
- 链上是否有边已经被另一条非树边覆盖
- 这条非树边所形成的环是否合法
可以用树剖 + 树状数组 / 线段树,需要实现链修改链查询。于是我们得到了一个 的做法。
实现得不太好的话会被卡常,所以讲个好写的 做法。
注意到每条边最多会被覆盖一次,所以修改链的时候可以暴力单点修改,于是问题变成了单点修改链查询。链查询还是得写树剖,所以树上差分一下变成子树修改单点查询,跑一遍 DFS 序,树状数组维护就行了。
值得注意的是这个图不一定连通,原图可能是一堆仙人掌。这个东西实际并不难处理,预处理 LCA 和 DFS 序的时候,对于每个连通块都跑一遍 DFS 就行了。
// 2021.07.31 - 09:09
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define debug printf("Passing Line %d in function [%s].\n",__LINE__,__FUNCTION__)
#define fi first
#define se second
inline int read(){
int x=0,f=1;
char ch='.';
while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return f*x;
}
inline void chmax(int &x,int y){x=max(x,y);}
inline void chmin(int &x,int y){x=min(x,y);}
const int MOD = 998244353;
inline int add(int x,int y){return(x+y>=MOD)?(x+y-MOD):((x+y<0)?(x+y+MOD):(x+y));}
const int MAXN = 300005, MAXM = 500005;
// data
int n, q;
int fr[MAXM], to[MAXM], val[MAXM];
vector<int> G[MAXN], H[MAXN];
bool ans[MAXM];
bool vis[MAXN];
// lca
int dep[MAXN];
int fa[23][MAXN];
void dfs1(int p, int par) {
fa[0][p] = par;
for (int i = 1; i <= 20; i++)
fa[i][p] = fa[i - 1][fa[i - 1][p]];
for (int i : G[p]) {
if (i != par) {
dep[i] = dep[p] + 1;
dfs1(i, p);
}
}
}
int lca(int x, int y) {
if (dep[x] < dep[y])
swap(x, y);
for (int i = 20; i >= 0; i--)
if (dep[fa[i][x]] >= dep[y]) x = fa[i][x];
if (x == y) return x;
for (int i = 20; i >= 0; i--)
if (fa[i][x] != fa[i][y])
x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
// dsu
int dsu_fa[MAXN];
inline int find(int x) {
if (dsu_fa[x] == x) return x;
return dsu_fa[x] = find(dsu_fa[x]);
}
// dfs_rank
int dfn[MAXN], id[MAXN], siz[MAXN];
int s[MAXN], a[MAXN];
int ind;
void dfs2(int p, int f) {
siz[p] = 1;
dfn[p] = ++ind;
id[ind] = p;
for (int j = 0; j < G[p].size(); j++) {
int i = G[p][j], w = H[p][j];
if (i == f) continue;
s[i] = s[p] + w;
dfs2(i, p);
siz[p] += siz[i];
}
}
// bit
struct BIT {
int tree[MAXN];
int max_value;
inline int lowbit(int x) {
return x & (-x);
}
inline void add(int x, int c) {
while (x <= max_value + 1) {
tree[x] += c;
x += lowbit(x);
}
}
inline int qry(int x) {
int ans = 0;
while (x > 0) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
inline int qry2(int l, int r) {
return qry(r) - qry(l - 1);
}
inline void add2(int l, int r, int c) {
add(l, c);
add(r + 1, -c);
}
}t1;
inline void upd(int x, int y, int l) {
while (x != l) {
t1.add2(dfn[x], dfn[x] + siz[x] - 1, 1);
x = fa[0][x];
}
while (y != l) {
t1.add2(dfn[y], dfn[y] + siz[y] - 1, 1);
y = fa[0][y];
}
}
signed main()
{
n = read(), q = read();
for (int i = 1; i <= n; i++)
dsu_fa[i] = i;
for (int i = 1; i <= q; i++) {
fr[i] = read(), to[i] = read(), val[i] = read();
int x = find(fr[i]), y = find(to[i]);
if (x != y) {
ans[i] = true;
dsu_fa[x] = y;
G[fr[i]].push_back(to[i]), H[fr[i]].push_back(val[i]);
G[to[i]].push_back(fr[i]), H[to[i]].push_back(val[i]);
}
}
for (int i = 1; i <= n; i++) {
if (!vis[find(i)]) {
vis[find(i)] = true;
dfs1(i, i);
dfs2(i, i);
}
}
t1.max_value = n;
for (int i = 1; i <= q; i++) {
if (ans[i]) continue;
int x = fr[i], y = to[i];
int l = lca(x, y);
int v1 = s[x] + s[y] - 2 * s[l] + val[i];
int v2 = t1.qry(dfn[x]) + t1.qry(dfn[y]) - 2 * t1.qry(dfn[l]);
if (v2 == 0 && v1 % 2 == 1) {
ans[i] = true;
upd(x, y, l);
}
}
for (int i = 1; i <= q; i++) {
if (ans[i]) puts("YES");
else puts("NO");
}
return 0;
}