题面

传送门

Sol

LCT维护子树和

# include <bits/stdc++.h>

# define IL inline

# define RG register

# define ls ch[0][x]

# define rs ch[1][x]

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(2e5 + 10);

IL ll Read(){

	RG char c = getchar(); RG ll x = 0, z = 1;

	for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

	for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

	return x * z;

}

int n, Q, ch[2][_], fa[_], size[_], sum[_], rev[_], S[_];

IL bool Son(RG int x){  return ch[1][fa[x]] == x;  }

IL bool Isroot(RG int x){  return ch[0][fa[x]] != x && ch[1][fa[x]] != x;  }

IL void Reverse(RG int x){  if(!x) return; swap(ls, rs); rev[x] ^= 1;  }

IL void Update(RG int x){  sum[x] = sum[ls] + sum[rs] + size[x] + 1;  }

IL void Pushdown(RG int x){  if(!rev[x]) return; Reverse(ls); Reverse(rs); rev[x] = 0;  }

IL void Rotate(RG int x){

	RG int y = fa[x], z = fa[y], c = Son(x);

	if(!Isroot(y)) ch[Son(y)][z] = x; fa[x] = z;

	ch[c][y] = ch[!c][x]; fa[ch[c][y]] = y;

	ch[!c][x] = y; fa[y] = x; Update(y);

}

IL void Splay(RG int x){

	S[S[0] = 1] = x;

	for(RG int y = x; !Isroot(y); y = fa[y]) S[++S[0]] = fa[y];

	while(S[0]) Pushdown(S[S[0]--]);

	for(RG int y = fa[x]; !Isroot(x); Rotate(x), y = fa[x])

		if(!Isroot(y)) Son(x) ^ Son(y) ? Rotate(x) : Rotate(y);

	Update(x);

}

IL void Access(RG int x){

	for(RG int y = 0; x; y = x, x = fa[x]) Splay(x), size[x] += sum[ch[1][x]] - sum[y], ch[1][x] = y, Update(x);

}

IL void Makeroot(RG int x){  Access(x); Splay(x); Reverse(x);  }

IL int Findroot(RG int x){  Access(x); Splay(x); while(ch[0][x]) x = ch[0][x]; return x;  }

IL void Link(RG int x, RG int y){  Makeroot(x); Makeroot(y); fa[x] = y; size[y] += sum[x]; Update(y);  }

int main(RG int argc, RG char* argv[]){

	freopen("dynamic_tree.in", "r", stdin); freopen("dynamic_tree.out", "w", stdout);

	n = Read(); Q = Read();

	while(Q--){

		RG int op = Read(), x = Read(), y, rt;

		if(op == 3) y = Read(), rt = Findroot(x), Link(x, y), Makeroot(rt);

		else if(op == 2) Access(x), printf("%d\n", size[x] + 1);

		else Makeroot(x);

	}

	return 0;

}