看题解里写的都是按秩合并的方法，我想试试用路径压缩，但不知为什么死活MLE，用了各种内存优化都不行

下面贴出代码，使用可持久化二叉搜索树（毕竟不用修改，就不用平衡树了）实现的可持久化数组，并在此之上实现的可持久化并查集。使用了#pragma pack(1)关闭结构体内存对齐，优化后从40pts->92ptx，但还是因为内存问题过不去。

#include <bits/extc++.h>

#pragma pack(1)

class immutable_array_t
{
public:
	struct node_t
	{
		int key;
		int value;
		node_t *left, *right;
		uint16_t mark;
	};

	node_t *bp, *sp, **root;
	int active;
	
	immutable_array_t(size_t pool_size, size_t version_size)
	{
		bp = (node_t *)malloc(sizeof(node_t) * pool_size);
		sp = bp;
		root = (node_t **)malloc(sizeof(node_t *) * version_size);
	}
	~immutable_array_t()
	{
		free(bp);
		free(root);
	}
	node_t *build_tree(int l, int r)
	{
		if (l > r)
			return NULL;
		int mid = (l + r) >> 1;
		node_t *node = bp + mid;
		node->key = mid;
		node->left = build_tree(l, mid - 1);
		node->right = build_tree(mid + 1, r);
		return node;
	}
	__always_inline void init(int max)
	{
		root[0] = build_tree(0, max - 1);
		sp += max;
	}

	__always_inline void safe_update_mark(node_t *node)
	{
		if (node != NULL)
			node->mark++;
	}

	__always_inline void copy_root(int origin)
	{
		active++;
		root[active] = sp++;
		*root[active] = *root[origin];
		safe_update_mark(root[active]->left);
		safe_update_mark(root[active]->right);
		root[active]->mark = 0;
	}

	// __always_inline int &simple_at(int key)
	// {
	// 	auto it = root[active];
	// 	while (it != NULL)
	// 	{
	// 		if (key < it->key)
	// 			it = it->left;
	// 		else if (key > it->key)
	// 			it = it->right;
	// 		else
	// 			return it->value;
	// 	}
	// 	assert(false);
	// }

	node_t *path_copy(node_t *it, int key, node_t *&target)
	{
		if (it->mark != 0)
		{
			*sp = *it;
			it->mark--;
			sp->mark = 0;
			it = sp++;
			safe_update_mark(it->left);
			safe_update_mark(it->right);
		}
		if (key < it->key)
			it->left = path_copy(it->left, key, target);
		else if (key > it->key)
			it->right = path_copy(it->right, key, target);
		else
			target = it;
		return it;
	}

	int find(int key)
	{
		node_t *target;
		path_copy(root[active], key, target);
		if (target->value != key)
			target->value = find(target->value);
		return target->value;
	}

	__always_inline void merge(int root_x, int root_y)
	{
		node_t *target;
		path_copy(root[active], root_x, target);
		target->value = root_y;
	}
	// __always_inline node_t *find(int key, int origin_version, int new_version)
	// {
	// 	root[new_version] = sp++;
	// 	*root[new_version] = *root[origin_version];
	// 	auto it = root[new_version];
	// 	while (it != NULL)
	// 	{
	// 		if (key < it->key)
	// 			it = it->left;
	// 		else if (key > it->key)
	// 			it = it->right;
	// 		else
	// 			return it;
	// 	}
	// 	return NULL;
	// }
};

immutable_array_t forest(5000000, 200001);
int n, m;
int op, a, b;

int main()
{
	// freopen64("P3402_11.in", "r", stdin);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		forest.bp[i].value = i;
	forest.init(n);
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &op);
		if (op == 1)
		{
			scanf("%d %d", &a, &b);
			a--;
			b--;
			forest.copy_root(i);
			forest.merge(forest.find(a), forest.find(b));
		}
		else if (op == 2)
		{
			scanf("%d", &op);
			forest.copy_root(op);
		}
		else
		{
			scanf("%d %d", &a, &b);
			a--;
			b--;
			forest.copy_root(i);
			printf(forest.find(a) == forest.find(b) ? "1\n" : "0\n");
		}
	}
	return 0;
}

求助！！！各位大佬能否解释一下为什么不能路径压缩，或者给出优化内存的方法。我分析我的空间复杂度应该给是 $O(n+mlgn)$，不应该啊