【洛谷 P4219】 [BJOI2014]大融合(LCT)

题目链接

维护子树信息向来不是\(LCT\)所擅长的，所以我没搞懂qwq

权当背背模板吧。Flash巨佬的blog里面写了虽然我没看懂。

#include <cstdio>

#define R register int

#define I inline void

#define lc c[x][0]

#define rc c[x][1]

const int MAXN = 300010;

inline int read(){

    int s = 0, w = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }

    while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }

    return s * w;

}

int f[MAXN], c[MAXN][2], v[MAXN], sz[MAXN], st[MAXN], tag[MAXN], ss[MAXN];

inline int nroot(R x){

	return c[f[x]][0] == x || c[f[x]][1] == x;

}

I pushup(R x){

	sz[x] = sz[lc] + sz[rc] + ss[x] + 1;

}

I pushdown(R x){

	if(tag[x]){

		R t = lc; lc = rc; rc = t;

		tag[lc] ^= 1; tag[rc] ^= 1; tag[x] = 0;

	}

}

I rotate(R x){

	R y = f[x], z = f[y], k = c[y][1] == x, w = c[x][!k];

	if(nroot(y)) c[z][c[z][1] == y] = x;

	c[x][!k] = y; c[y][k] = w; f[y] = x; f[x] = z;

	if(w) f[w] = y;

	pushup(y);

}

I pushall(R x){

    if(nroot(x)) pushall(f[x]);

    pushdown(x);

}

I splay(R x){

	pushall(x);

	while(nroot(x)) rotate(x);

	pushup(x);

}

I access(R x){

	for(R y = 0; x; x = f[y = x]){

	   splay(x); ss[x] += sz[rc]; ss[x] -= sz[rc = y]; pushup(x);

    }

}

I makeroot(R x){

	access(x); splay(x);

	tag[x] ^= 1;

}

I split(R x, R y){

	makeroot(x); access(y); splay(y);

}

I link(R x, R y){

	split(x, y);

	ss[f[x] = y] += sz[x];

	pushup(y);

}

int n, m, a, b;

char opt;

int main(){

	n = read(); m = read();

	for(R i = 1; i <= n; ++i) sz[i] = 1;

	while(m--){

		opt = getchar(); while(opt != 'A' && opt != 'Q') opt = getchar();

		 a = read(); b = read();

		switch(opt){

			case 'Q' : split(a, b); printf("%lld\n", (long long)(ss[a] + 1) * (ss[b] + 1)); break;

			case 'A' : link(a, b); break;

		}

	}

	return 0;

}