My friend gave me an interesting problem:
Given connected, weighted graph with N nodes and M edges. There are Q queries, each of two types:
- Type 1:
1 iRemove edge numbered $$$i$$$ $$$(1 \le i \le M)$$$ - Type 2:
2 u vFind a path from u to v with the minimum total XOR value (edges may be traversed multiple times). If no path exists, return $$$–1$$$.
Constraints:
$$$(1 ≤ N, M, Q ≤ 2×10^5)$$$
$$$(1 ≤ u,v ≤ N; 0 ≤ w ≤ 10^9)$$$
You have link to sumbit this problem?
You can solve this problem by going through the queries in reverse order(so we only add edges). If the edge does not form a cycle add the edge to DSU with appropriate weight (XORed with all weights up to the DSU roots of vertices the edge connects). If an edge would form a cycle, we can notice that we can use that cycle in a simple path either 0 or 1 time(even when there a lot of cycles, we can choose which cycles to take or not).
This reduces answering the queries to: given a set S and a number x, find the smallest XOR value you can obtain by XORing x with some numbers from S. We can solve this problem using XOR basis. For additional explanations you can check out this task (your task, but with adding edges too).