Idea
Each edge exists in [add_time, remove_time). Insert into segment tree over time indices. DFS over tree, unioning + rolling back.
Advertisement
Segment tree structure
Leaves = time points. Each edge added to O(log Q) segment nodes covering its lifetime.
Advertisement
DFS
At each node: union all edges stored there. Recurse to children. On way back, rollback. At leaves, answer queries.
Complexity
O((N + Q) log² N). Two log factors: segment tree + DSU without compression.