$RT$，学的时候说不能使用路径压缩，因为会爆空间。但是如果我在查询的时候使用的是引用，然后直接对叶子结点值进行修改，不就不用新开一条链了吗？改了之后发现确实快了一些，但是有测试点WA了，各位能帮我看一下嘛 ^O^

测评记录

Code：

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

const int N = 1e5 + 10, M = 2e5 + 10;
struct
{
	int son[2], l, r, val;
} t[N * 2 * 2 + M * 17 * 2];
#define lc(k) t[k].son[0]
#define rc(k) t[k].son[1]
int rootfa[M], tot;
void build(int &k, int l, int r)
{
	k = ++tot;
	t[k].l = l, t[k].r = r;
	if (l == r)
	{
		t[k].val = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(lc(k), l, mid);
	build(rc(k), mid + 1, r);
}
void update(int oldk, int &k, int p, int x)
{
	k = ++tot;
	t[k] = t[oldk];
	if (t[k].l == t[k].r)
	{
		t[k].val = x;
		return;
	}
	int mid = (t[k].l + t[k].r) >> 1;
	if (p <= mid)
		update(lc(oldk), lc(k), p, x);
	else
		update(rc(oldk), rc(k), p, x);
}
int &query(int k, int p)
{
	if (t[k].l == t[k].r)
		return t[k].val;
	int mid = (t[k].l + t[k].r) >> 1;
	if (p <= mid)
		return query(lc(k), p);
	else
		return query(rc(k), p);
}
int find(int ver, int x)
{
	int &fa = query(rootfa[ver], x);
	return fa == x ? x : fa = find(ver, fa);
	// 如果路径压缩，那每一个路径上的结点都要新开一条链
	// 最坏情况：前1e5次构建一条链，后边一直以1e5次为版本对根和叶进行查询，那么就要1e5（询问）*1e5（深度，链上的所有节点）*log(1e5)个结点，MLE
}
void merge(int ver, int x, int y)
{
	x = find(ver, x), y = find(ver, y);
	if (x == y)
	{
		rootfa[ver] = rootfa[ver - 1];
		return;
	}
	update(rootfa[ver - 1], rootfa[ver], x, y);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	// freopen("test.txt", "r", stdin);
	// freopen("out.out", "w", stdout);
	int n, m, a, b, k;
	char op;
	cin >> n >> m;
	build(rootfa[0], 1, n);
	for (int ver = 1; ver <= m; ++ver)
	{
		cin >> op;
		if (op == '1')
		{
			cin >> a >> b;
			rootfa[ver] = rootfa[ver - 1];
			merge(ver, a, b);
		}
		else if (op == '2')
		{
			cin >> k;
			rootfa[ver] = rootfa[k];
		}
		else
		{
			cin >> a >> b;
			rootfa[ver] = rootfa[ver - 1];
			cout << (find(ver, a) == find(ver, b) ? "1\n" : "0\n");
		}
	}
	return 0;
}