女生刚学 OI 求调 TLE 82pts.

#include <iostream>
using namespace std;
int a[1000005], I[24000000], love[24000000], seele[24000000], forever=1, rt[24000000], sz[24000000], n;
void build(int l, int r, int n) {
if (l == r) {seele[n] = l; 
sz[n] = 1; return;}
build(l, (l + r) >> 1, I[n] = ++forever); build(((l + r) >> 1) + 1, r, love[n] = ++forever);
}
int query(int l, int r, int n, int x) {
if (l == r) return seele[n];
if (x <= (l + r) >> 1) return query(l, (l + r) >> 1, I[n], x); return query(((l + r) >> 1) + 1, r, love[n], x);
}
int querysz(int l, int r, int n, int x) {
if (l == r) return sz[n];
if (x <= (l + r) >> 1) return querysz(l, (l + r) >> 1, I[n], x); return querysz(((l + r) >> 1) + 1, r, love[n], x);
}
void update(int l, int r, int n, int x, int v, int s, int d) {
I[n] = I[d]; love[n] = love[d]; if (l == r) {seele[n] = v; sz[n] = s; return;}
if (x <= (l + r) >> 1) {update(l, (l + r) >> 1, I[n] = ++forever, x, v, s, I[d]); return;} update(((l + r) >> 1) + 1, r, love[n] = ++forever, x, v, s, love[d]);
}
int find(int x, int rt) {if (query(1, n, rt, x) == x) return x; else return find(query(1, n, rt, x), rt);}
int main() {ios::sync_with_stdio(0);
int m, v, op, x, y; cin >> n >> m; rt[0] = 1; build(1, n, 1);
for (int i=1; i<=m; i++) {cin >> op;
if (op == 1) {cin >> x >> y; int xx = find(x, rt[i-1]); int yy = find(y, rt[i-1]); if (querysz(1, n, rt[i-1], xx) > querysz(1, n, rt[i-1], yy)) swap(xx, yy); if (xx != yy) update(1, n, rt[i] = ++forever, yy, xx, querysz(1, n, rt[i-1], xx) + querysz(1, n, rt[i-1], yy), rt[i-1]); else rt[i] = rt[i-1];
} if (op == 2) {cin >> v; rt[i] = rt[v];} if (op == 3) {cin >> x >> y; rt[i] = rt[i-1]; cout << (query(1, n, rt[i], find(x, rt[i])) == query(1, n, rt[i], find(y, rt[i]))) << endl;}
}}