不知道为啥，有时候写的 LCT 会 MLE。

#include <stdio.h>
#define Maxn 500004
#define ll long long

struct Link_Cut_Tree {
	#define swap(u, v) u ^= v ^= u ^= v
	int fa[Maxn], ch[Maxn][2], g[Maxn], siz[Maxn];
	bool r[Maxn]; 
	
	bool nroot(int u) {
		return ch[fa[u]][0] == u || ch[fa[u]][1] == u;
	} 
	
	bool which(int u) {
		return ch[fa[u]][1] == u;
 	}
 	
	void push_up(int x) {
		siz[x] = siz[ch[x][1]] + siz[ch[x][0]] + g[x] + 1;
 	}
	
	void push_down(int x) {
		if(r[x]) {
			swap(ch[x][1], ch[x][0]);
			r[ch[x][1]] ^= 1, r[ch[x][0]] ^= 1;
			r[x] = 0;
		}
	}
	
	void rotate(int x) {
		int y = fa[x], z = fa[y];
		push_down(z), push_down(y), push_down(x);
		bool w = which(x);
		if(nroot(y)) ch[z][which(y)] = x; fa[x] = z;
		ch[y][w] = ch[x][w ^ 1], fa[ch[x][w ^ 1]] = y;
		ch[x][w ^ 1] = y, fa[y] = x;
		push_up(y), push_up(x);
 	}
 	
 	void upd(int x) {
 		if(nroot(x)) upd(fa[x]);
 		push_down(x);
	}
 	
 	void splay(int x) {
 		upd(x);
 		for(int y; y = fa[x], nroot(x); rotate(x)) 
 			if(nroot(y)) rotate(which(x) == which(y) ? y : x);
	}
	
	void access(int x) {
		for(int p = 0; x; x = fa[p = x]) {
			splay(x), g[x] += siz[ch[x][1]] - siz[p];
			ch[x][1] = p; push_up(x);
		}
	}
	
	void makeroot(int x) {
		access(x), splay(x);
		r[x] ^= 1;
	}
	
	void link(int x, int y) {
		makeroot(x); 
 		fa[x] = y, g[y] += siz[x];
		push_up(y); 
	}
	
	void cut(int x, int y) {
		makeroot(x), access(y);
		fa[x] = ch[y][0] = 0;
		push_up(y);
	}
	
	ll query(int x, int y) {
		cut(x, y); int a, b;
		makeroot(x), a = siz[x];
		makeroot(y), b = siz[y];
		link(x, y); return (ll)a * b;
	}
}LCT;

int n, m;

int main() {
	scanf("%d%d", &n, &m); char c; int x, y;
	for(int i = 1; i <= n; ++ i) LCT.siz[i] = 1;
	
	while(m --) {
		scanf("%s%d%d", &c, &x, &y); 
		if(c == 'A') LCT.link(x, y);
		else printf("%lld\n", LCT.query(x, y));
	}
	
}