RT，可持久化并查集写炸了，貌似是按秩合并写错了。代码还算能看，求调悬关

提交记录，难道是常数问题吗，QwQ

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

const int N = 1e5 + 5; 
int n, m, opt, a, b, fa;
int rot[N << 1];

namespace Segment_Tree{
	#define mid (l + r >> 1)
	
	int ls[N * 45], rs[N * 45], id[N * 45], dep[N * 45], tot;
	
	inline void to(int ua, int ub) {ls[ub] = ls[ua], rs[ub] = rs[ua], dep[ub] = dep[ua], id[ub] = id[ua];}
	inline void change(int &u, int l, int r, int k, int c, int flag){ //修改原有版本
		if(!u) u = ++tot;
		if(l == r){
			if(flag == 1) id[u] = c;
			else dep[u] = c;
			return ;
		}
		if(k <= mid) change(ls[u], l, mid, k, c, flag);
		else change(rs[u], mid + 1, r, k, c, flag);
	}
	inline void upd(int ua, int &ub, int l, int r, int k, int c, int flag){
		ub = ++tot, to(ua, ub);
		if(l == r){
			if(flag == 1) id[ub] = c;
			else dep[ub] = c;
			return ;
		}
		if(k <= mid) upd(ls[ua], ls[ub], l, mid, k, c, flag);
		else upd(rs[ua], rs[ub], mid + 1, r, k, c, flag);
	}
	inline int query(int u, int l, int r, int k, int flag){
		if(l == r) return flag == 1 ? id[u] : dep[u];
		if(k <= mid) return query(ls[u], l, mid, k, flag);
		else return query(rs[u], mid + 1, r, k, flag);
	}
}
using namespace Segment_Tree;
inline int find(int u, int hst){
	fa = query(rot[hst], 1, n, u, 1);
	return fa == u ? u : find(fa, hst);
}
inline void mer(int x, int y, int hst, int now){
	x = find(x, hst), y = find(y, hst);
	if(x == y){
		rot[now] = rot[hst];
		return ;
	}
	int sx = query(rot[hst], 1, n, x, 2), sy = query(rot[hst], 1, n, y, 2);
	if(sx > sy) swap(x, y), swap(sx, sy);
	upd(rot[hst], rot[now], 1, n, x, y, 1); //先创建新版本
	change(rot[now], 1, n, y, max(sy, sx + 1), 2); //再在这个版本上更改深度
}
signed main(){
	cin >> n >> m;
	for(int i = 1; i <= n;++i){
		change(rot[0], 1, n, i, i, 1);
		change(rot[0], 1, n, i, 1, 2);
	}
	for(int i = 1; i <= m;++i){
		scanf("%d%d", &opt, &a);
		if(opt == 2) rot[i] = rot[a];
		else{
			scanf("%d", &b);
			if(opt == 1) mer(a, b, i - 1, i);
			else{
				rot[i] = rot[i - 1];
				printf("%d\n", find(a, i) == find(b, i));
			}
		}
	}
	return 0;
}