Good Graph
Contest: Educational Codeforces Round 112 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, dsu, graphs, trees

You have an undirected graph consisting of $$$n$$$ vertices with weighted edges.

A simple cycle is a cycle of the graph without repeated vertices. Let the weight of the cycle be the XOR of weights of edges it consists of.

Let's say the graph is good if all its simple cycles have weight $$$1$$$. A graph is bad if it's not good.

Initially, the graph is empty. Then $$$q$$$ queries follow. Each query has the next type:

- $$$u$$$ $$$v$$$ $$$x$$$ — add edge between vertices $$$u$$$ and $$$v$$$ of weight $$$x$$$ if it doesn't make the graph bad.

For each query print, was the edge added or not.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n \le 3 \cdot 10^5$$$; $$$1 \le q \le 5 \cdot 10^5$$$) — the number of vertices and queries.

Next $$$q$$$ lines contain queries — one per line. Each query contains three integers $$$u$$$, $$$v$$$ and $$$x$$$ ($$$1 \le u, v \le n$$$; $$$u \neq v$$$; $$$0 \le x \le 1$$$) — the vertices of the edge and its weight.

It's guaranteed that there are no multiple edges in the input.

Output format:
For each query, print YES if the edge was added to the graph, or NO otherwise (both case-insensitive).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
9 12
6 1 0
1 3 1
3 6 0
6 2 0
6 4 1
3 4 1
2 4 0
2 5 0
4 5 0
7 8 1
8 9 1
9 7 0

Example output:
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO

Editorial:
Firstly, let's prove that a good graph has one important property: any two of its simple cycles intersect by at most one vertex, i. e. there is no edge that belongs to more than one simple cycle (cactus definition, yeah).
Let's prove it by showing that if two simple cycles of weight $$$k > 0$$$ intersects (by edges) then they will induce a simple cycle of weight $$$\neq k$$$. There are two cases:
• if cycles intersect by a single path, then we can create a new cycle by merging parts of cycles excluding the intersecting path — it will be simple and will have weight $$$k \oplus k = 0 \neq k$$$;
• if cycles intersect by more than one path, we can do the next transformation: suppose the common paths are $$$u_1 - v_1$$$, $$$u_2 - v_2$$$, $$$\dots$$$, and they are ordered in the way how they lie on the first cycle. Let's create a third cycle using two paths from $$$v_1$$$ to $$$u_2$$$: from the first cycle and from the second cycle. It's easy to see that the third cycle is simple, and more over it has only one common path with the second cycle. So, it's either the third cycle has weight not equal to $$$k$$$ or the case $$$1$$$.
Okay, let's analyze the edges we try to add. Let's divide all edges in two types: tree edges and all other edges (we will name them cycle edges). Let's name an edge as a tree edge if it connects two different components at a moment when we are trying to add it in the graph.
It's obvious that we will add all tree edges in the graph, since they can't make it bad (since they don't induce new cycles). But there is a more interesting observation: when we try to add a cycle edge $$$(u, v)$$$, it should induce an only one simple cycle where all other edges are tree edges and these tree edges can't be used in any other cycle.
It induces at least one "all-tree-edge" cycle, since $$$u$$$ and $$$v$$$ are already connected. It can't induce more than one "all-tree-edge" cycle, since it contradicts with tree edge definition, and if it induces a cycle with some other cycle edge, then we can replace that cycle edge with its own tree-edge path: our cycle will become "all-tree-edge" cycle, but it will use already used tree edges. In other words, it's enough to consider only one "all-tree-edge" cycle induced by any cycle edge.
The final trick is to calculate the answer in two steps: at the first step, we will find only tree edges (using DSU) that will form a spanning forest in our graph.
The second step is for each cycle edge $$$(u, v)$$$ to calculate the $$$\operatorname{XOR}$$$ $$$X$$$ on a path between $$$u$$$ and $$$v$$$ in our spanning forest, check that $$$X \oplus \text{edge_weight} = 1$$$ and check that none of edges on the path from $$$u$$$ to $$$v$$$ are used in other cycle.
Calculating $$$X$$$ is easy: if we precalculate for each vertex $$$v$$$ the $$$\operatorname{XOR}$$$ on path from $$$v$$$ to root $$$\mathit{xr}[v]$$$ then $$$X = \mathit{xr}[u] \oplus \mathit{xr}[v]$$$.
Checking that none of the edges are used on the path from $$$u$$$ to $$$v$$$ is a bit tricky: if we mark an edge by adding $$$1$$$ to it, then we should be able to take a sum on path and add on path. There are structures that are capable of it (like HLD and other), but let's look closely.
Note that we mark each tree edge at most once, so we can manually add $$$1$$$ to each edge, and only asking sum on path should be fast. In other words, we need a data structure (DS) that can add value at edge and take the sum on path — and such DS is a Fenwick tree (BIT) built on Euler tour of tree: it can add value at edge and ask a sum on path from $$$v$$$ to root. So we need to find LCA as well, since sum of path $$$(u, v)$$$ is equal to $$$sum(u) + sum(v) - 2 \cdot sum(LCA(u, v))$$$.
As a result, complexity is $$$O((n + m) \log(n))$$$ with quite a low constant from LCA and BIT.