Jan 19, 2023

CF1555F

称权值异或和为的简单环为合法的环。

假设两个合法的环有至少一条公共边，那么考虑它们组成的大环的权值：每条公共边上的权值相同可以抵消，其他边上的权值异或和相同，也抵消，则大环的权值为 ——显然这两个环组成的大环不是合法的，所以原图一定是一个仙人掌状物。

然后考虑仙人掌是个什么样的东西：对它建出 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;
}