Hints: Incremental Even-Weighted Cycle Queries
Answer to Hint 1: The total weight on a cycle is even iff the sum modulo $2$ is $0$. With weights in ${0,1}$, that is the same as the XOR of the cycle’s edge weights being $0$.
Try to relate “every cycle has XOR sum $0$” to putting a value in ${0,1}$ on each vertex. If you imagine walking an edge $(u,v,w)$, what equation should $b[u]$ and $b[v]$ satisfy if $b[\cdot]$ is meant to “explain” the edge weight?
Answer to Hint 2: A standard reformulation: you want labels $b[0],\ldots,b[n-1] \in {0,1}$ such that for every present edge $(u,v,w)$,
$$ b[u] \oplus b[v] = w $$
(XOR on the right since $w\in{0,1}$.)
If such labels exist, traversing any closed walk makes the XOR of edge weights equal to $b[\text{start}] \oplus b[\text{start}] = 0$. So the global condition is local XOR consistency along edges.
You are not given $b$ up front; you grow the edge set. What data structure is natural for “which vertices are already tied together,” while remembering relative XOR along a chosen spanning structure?
Answer to Hint 3: Use a disjoint-set (union–find) on vertices. For each node, also store the XOR of weights along the path to its parent (in the DSU forest). During find, compress paths while updating these XORs so each node knows its XOR to the component “root.”
Before processing an edge $(u,v,w)$, compute the XOR from $u$ to the root of its component and from $v$ to the root of its component. What two cases arise depending on whether $u$ and $v$ are already in the same component?
Answer to Hint 4: Let $p(u)$ be the XOR from $u$ to its DSU root (after find). Similarly $p(v)$.
-
If $u$ and $v$ are in different components, adding $(u,v,w)$ cannot close a cycle yet: you can always merge and choose parent pointers so the new tree edge is consistent with the existing XOR labels. This edge should count as added.
-
If they are in the same component, there is already a $u$–$v$ path in the forest. The new edge would form cycles; consistency requires that the XOR along the existing $u$–$v$ path equals $w$. In XOR terms, what equation must $p(u)$, $p(v)$, and $w$ satisfy?
Answer to Hint 5: Along the old path, the XOR from $u$ to $v$ is $p(u) \oplus p(v)$. The new edge is compatible iff
$$ p(u) \oplus p(v) = w. $$
If equality holds, adding the edge does not contradict the labeling (odd cycles cannot appear); count it as added. If not, reject the edge.
When merging two different components, one root must become the child of the other: how can you set the XOR on the new parent link so that the edge $(u,v,w)$ matches the implied values at $u$ and $v$?
Answer to Hint 6: If $r_u$ and $r_v$ are the roots with $p(u)$, $p(v)$ known, and (say) you attach $r_u$ under $r_v$, you need a value $x$ on the new parent edge so that the extended labels stay consistent—solve for $x$ from $p(u)$, $p(v)$, and $w$ using XOR algebra. Union-by-rank (or size) still applies; only the root’s parent XOR needs to be chosen correctly.
With path compression, remember to push XOR through when shortening paths: when $x$ jumps to its parent, its accumulated XOR to the root must update by XORing with the parent’s XOR to the root.
What overall time complexity does this achieve for $n, |E| \le 5\cdot 10^4$?
Answer to Hint 7: Amortized nearly constant time per edge for union–find with path compression (standard $\alpha(n)$ inverse-Ackermann), so about $O((n + m),\alpha(n))$, easily within limits.
The answer is the count of edges that are either successful merges or same-component additions that pass the $p(u)\oplus p(v)=w$ test.