持久并查集（Persistent Unionfind）

问题描述

设 $G_{-1}$ 为一个含 $N$ 个顶点、无边的图。
处理 $Q$ 个查询，第 $i$ 个查询形式如下：

• 0 k_i u_i v_i：令 $G_i$ 为在 $G_{k_i}$ 中添加边 $(u_i, v_i)$ 所得的图。
• 1 k_i u_i v_i：若顶点 $u_i$ 与 $v_i$ 在 $G_{k_i}$ 中连通输出 1；否则输出 0。

约束说明：对所有 $i$，$k_i = -1$ 或 $k_i = 0$，即每次操作基于初始图或前一个图。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $t_i \in \{0, 1\}$
• $-1 \leq k_i < i$
• 对所有 $k_i$，有 $k_i = -1$ 或 $k_i = 0$
• $0 \leq u_i, v_i < N$

输入

$N\ Q$
$t_0\ k_0\ u_0\ v_0$
$t_1\ k_1\ u_1\ v_1$
:
$t_{Q-1}\ k_{Q-1}\ u_{Q-1}\ v_{Q-1}$

5 12
0 -1 0 1
0 0 0 2
1 -1 0 1
1 0 0 1
1 1 0 1
0 1 3 4
0 1 2 3
1 5 1 4
0 5 2 3
1 8 1 4
0 6 3 4
1 10 1 4

0
1
1
0
1
1