可持久化并查集

【题目描述】

设 $G_{-1}$ 为包含 $N$ 个顶点且没有边的图。依次处理 $Q$ 个查询。第 $i$ 个查询按以下格式给出：

• 0 $k_{i}$ $u_{i}$ $v_{i}$：令 $G_{i}$ 为在 $G_{k_{i}}$ 中加入一条边 $\left( u, v \right)$ 所得到的图。
• 1 $k_{i}$ $u_{i}$ $v_{i}$：若 $G_{k_{i}}$ 中的顶点 $u, v$ 连通，输出 $1$；否则输出 $0$。

【输入】

$N$ $Q$
$t_0$ $k_0$ $u_0$ $v_0$
$\vdots$
$t_{Q-1}$ $k_{Q-1}$ $u_{Q-1}$ $v_{Q-1}$

【输出】

对每个 1 $k_{i}$ $u_{i}$ $v_{i}$ 查询，若 $G_{k_{i}}$ 中顶点 $u$ 与 $v$ 连通则输出一行 $1$，否则输出一行 $0$。

【输入样例】

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

【数据范围】

• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $t_{i} \in \left\lbrace 0, 1 \right\rbrace$
• $-1 \leq k_{i} < i$
• 对所有 $k_{i}$，都有 $k_{i} = -1$ 或 $t_{k_{i}} = 0$。
• $0 \leq u_{i}, v_{i} < N$

【来源】

Library Checker（yosupo06） persistent_unionfind