Explanation

This problem can be solved using Heavy-Light Decomposition. In the segment tree, toggle sets a node’s position if it is black, or INF if it is white. For path queries, HLD breaks the path into segments and takes the minimum position over them. If the result is INF, the answer is -1. Otherwise, it is mapped back to the node index using inv[].

Implementation

Time Complexity: $\mathcal{O}(\log^2N)$ per query

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Segment Tree (Click to expand)

 Code Snippet: HLD (Click to expand)

int main() {
	int n, q;
	cin >> n >> q;