YS - Perisistent Union Find

Explanation

Using a data structure that can undo any past consecutive changes, we can solve this problem by processing queries offline. Let's construct a directed graph of queries. The $u$'th query and the $v$'th query has a directed edge iff $k_v = u$, in other words, the $v$'th query is using the graph from query $u$. Thus using DFS, when we recurse through the graph we are simply processing queries, and when we exit our recursion we are simply undoing queries (this is possible due to using rollbacks)!

Implementation

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

struct DSU {
	vector<int> p, sz;
	// stores info from the past
	vector<pair<int, int>> past_parent, past_size;
	DSU(int n) {
		p.resize(n);
		sz.resize(n, 1);