rt，以这题为例，一棵普通的可持久化线段树空间大概 $\max_N \times 2^5$，在其基础上建立可持久化并查集，那么其空间理论会消耗多少？

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

const int N = 2e5 + 5;

int n, m, op, q, l, r, k, a, b;

struct PDSU {
	struct SegmentTree {
		int l, r, fa, dep;

#define l(p) t[p].l
#define r(p) t[p].r
#define fa(p) t[p].fa
#define dep(p) t[p].dep
	} t[N * 75];

	int cnt = 0, rt[N] = {};

	int build(int l, int r) {
		int p = ++cnt;
		if(l == r) {
			fa(p) = l;
			return p;
		}
		int mid = l + r >> 1;
		l(p) = build(l, mid), r(p) = build(mid + 1, r);
		return p;
	}

	int ask(int p, int l, int r, int k) {
		if(l == r)
			return p;
		int mid = l + r >> 1;
		if(k <= mid)
			return ask(l(p), l, mid, k);
		else
			return ask(r(p), mid + 1, r, k);
	}

	inline int get(int p, int k) {
		int Fa = ask(rt[p], 1, n, k);
		if(fa(Fa) == k)
			return Fa;
		return get(p, fa(Fa));
	}
	
	inline int News(int p) {
		int P = ++cnt;
		rt[P] = rt[p];
		return P;
	}
	
	inline int setfa(int p, int l, int r, int u, int v) {
		int P = News(p);
		if(l == r) {
			fa(P) = v;
			return P;
		}
		int mid = l + r >> 1;
		if(u <= mid)
			l(P) = setfa(l(p), l, mid, u, v);
		else
			r(P) = setfa(r(p), mid + 1, r, u, v);
		return P;
	}
	
	inline int add(int p, int l, int r, int k) {
		int P = News(p);
		if(l == r) {
			++dep(P);
			return P;
		}
		int mid = l + r >> 1;
		if(k <= mid)
			l(P) = add(l(p), l, mid, k);
		else
			r(P) = add(r(p), mid + 1, r, k);
		return P;
	}
	
	void merge(int p, int a, int b) {
		rt[p] = rt[p - 1];
		int A = get(p, a), B = get(p, b);
		if(fa(A) != fa(B)) {
			if(dep(A) > dep(B)) swap(A, B);
			rt[p] = setfa(rt[p - 1], 1, n, fa(A), fa(B));
			if(dep(A) == dep(B))
				rt[p] = add(rt[p], 1, n, fa(B));
		}
	}
	
	bool check(int p, int a, int b) {
		int A = get(p, a), B = get(p, b);	
		return fa(A) == fa(B);
	}

} DSU;



signed main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> n >> q, DSU.rt[0] = DSU.build(1, n);
	for(int i = 1; i <= q; ++i) {
		cin >> op >> a;
		if(op == 1) 
			cin >> b, DSU.merge(i, a, b);
		else if(op == 2)
			DSU.rt[i] = DSU.rt[a];
		else
			cin >> b, cout << DSU.check(i - 1, a, b) << '\n', DSU.rt[i] = DSU.rt[i - 1];
 	}
}

WA 60。