P3402
我用快读就几乎全WA,4tps
不用会部分TLE,但其余点都AC,76tps
有没有人知道快读有什么bug吗

不用快读

#include <bits/stdc++.h>

#define N 200005

using namespace std;

int n, m, rt[N], tot;
struct tree {
	int lp, rp, fa, dep;
} t[N << 4];

void build(int &p, int l, int r) {
	if(!p) p = ++tot;
	if(l == r) {
		t[p].fa = l, t[p].dep = 1; return ;
	}
	int mid = l + r >> 1;
	build(t[p].lp, l, mid), build(t[p].rp, mid + 1, r);
}

int clone(int p) {
	t[++tot] = t[p]; return tot;
}

void modify(int &p, int l, int r, int pos, int k, int fg) {
	if(!p) p = ++tot;
	else if(fg) p = clone(p);
	if(l == r) {
		if(fg) t[p].fa = k;
		else t[p].dep = k;
		return ;
	}
	int mid = l + r >> 1;
	if(pos <= mid) modify(t[p].lp, l, mid, pos, k, fg);
	else modify(t[p].rp, mid + 1, r, pos, k, fg);
}

pair<int, int> get(int p, int l, int r, int pos) {
	if(l == r) return make_pair(t[p].fa, t[p].dep);
	int mid = l + r >> 1;
	if(pos <= mid) return get(t[p].lp, l, mid, pos);
	return get(t[p].rp, mid + 1, r, pos);
}

int find(int t, int x) {
	pair<int, int> tmp = get(rt[t], 1, n, x);
	if(tmp.first == x) return x;
	return find(t, tmp.first);
}

bool same(int t, int a, int b) {
	return find(t, a) == find(t, b);
}

void meg(int t, int a, int b) {
	int na = find(t - 1, a), nb = find(t - 1, b);
	int dna = get(t - 1, 1, n, na).second, dnb = get(t - 1, 1, n, nb).second;
	rt[t] = rt[t - 1];
	if(na == nb) return ;
	if(dna == dnb) {
		modify(rt[t], 1, n, na, nb, 1);
		modify(rt[t], 1, n, na, dnb + 1, 0);
		return ;
	}
	if(dna > dnb) swap(na, nb), swap(dna, dnb);
	modify(rt[t], 1, n, na, nb, 1);
	modify(rt[t], 1, n, na, dnb, 0);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	build(rt[0], 1, n);
	for (int i = 1; i <= m; ++i) {
		int op, x, y; cin >> op;
		if(op == 1) {
			cin >> x >> y;
			meg(i, x, y);
		}
		else if(op == 2) cin >> x, rt[i] = rt[x];
		else {
			cin >> x >> y;
			cout << same(i - 1, x, y) << '\n';
			rt[i] = rt[i - 1];
		}
	}
}

用了快读

#include <bits/stdc++.h>

#define N 200005

using namespace std;

int read() {
	int x = 0, y = 1; char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) x = (x << 3 | x << 1) + c - '0', c = getchar();
	return x * y;
}

int n, m, rt[N], tot;
struct tree {
	int lp, rp, fa, dep;
} t[N << 4];

void build(int &p, int l, int r) {
	if(!p) p = ++tot;
	if(l == r) {
		t[p].fa = l, t[p].dep = 1; return ;
	}
	int mid = l + r >> 1;
	build(t[p].lp, l, mid), build(t[p].rp, mid + 1, r);
}

int clone(int p) {
	t[++tot] = t[p]; return tot;
}

void modify(int &p, int l, int r, int pos, int k, int fg) {
	if(!p) p = ++tot;
	else if(fg) p = clone(p);
	if(l == r) {
		if(fg) t[p].fa = k;
		else t[p].dep = k;
		return ;
	}
	int mid = l + r >> 1;
	if(pos <= mid) modify(t[p].lp, l, mid, pos, k, fg);
	else modify(t[p].rp, mid + 1, r, pos, k, fg);
}

pair<int, int> get(int p, int l, int r, int pos) {
	if(l == r) return make_pair(t[p].fa, t[p].dep);
	int mid = l + r >> 1;
	if(pos <= mid) return get(t[p].lp, l, mid, pos);
	return get(t[p].rp, mid + 1, r, pos);
}

int find(int t, int x) {
	pair<int, int> tmp = get(rt[t], 1, n, x);
	if(tmp.first == x) return x;
	return find(t, tmp.first);
}

bool same(int t, int a, int b) {
	return find(t, a) == find(t, b);
}

void meg(int t, int a, int b) {
	int na = find(t - 1, a), nb = find(t - 1, b);
	int dna = get(t - 1, 1, n, na).second, dnb = get(t - 1, 1, n, nb).second;
	rt[t] = rt[t - 1];
	if(na == nb) return ;
	if(dna == dnb) {
		modify(rt[t], 1, n, na, nb, 1);
		modify(rt[t], 1, n, na, dnb + 1, 0);
		return ;
	}
	if(dna > dnb) swap(na, nb), swap(dna, dnb);
	modify(rt[t], 1, n, na, nb, 1);
	modify(rt[t], 1, n, na, dnb, 0);
}

int main() {
	n = read(), m = read();
	build(rt[0], 1, n);
	for (int i = 1; i <= m; ++i) {
		int op, x, y; op = read();
		if(op == 1) {
			x = read(), y = read();
			meg(i, x, y);
		}
		else if(op == 2) x = read(), rt[i] = rt[x];
		else {
			x = read(), y = read();
			if(same(i - 1, x, y)) puts("1");
			else puts("0");
			rt[i] = rt[i - 1];
		}
	}
}