树上询问

题目链接：ybtoj高效进阶 21185

题目大意

给你一个森林，一开始有 n 个点，然后要支持三个操作：
把一个点定做它树的根，查询一个点子树大小，连接两个不在同一棵树上的点，然后指定其中一个树原来的根是新树的根。

思路

小前言

这题改半天一直都是 5 5 5 分，结果叫别人叫他的 AC 代码也只有 5 5 5 分？！
好我不管了我摆烂了我宣布我 A 了爱改不改。

正式内容

其实就是 LCT 维护子树内容题。

大概就是维护包括实边虚边的子树大小，以及虚边连接的子树大小。

这样维护有什么用呢？
你会发现你可以把实边设做它在森林中的父亲，那你设置根的操作就相当于 access 操作。

然后维护一下即可。

代码

#include<cstdio>
#include<algorithm>

using namespace std;

int n, m, op, x, y, rt;

int re, zf;
char c;

int read() {
	re = 0; zf = 1;
	c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') zf = -zf;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0';
		c = getchar();
	}
	return re * zf;
}

void writee(int now) {
	if (now > 9) writee(now / 10);
	putchar(now % 10 + '0');
}

void write(int now) {
	if (now < 0) putchar('-'), now = -now;
	writee(now);
}

struct LCT {
	int sum[400001], faksz[400001];
	int ls[400001], rs[400001], fa[400001];
	bool lzyt[400001];
	
	bool nrt(int x) {
		return ls[fa[x]] == x || rs[fa[x]] == x;
	}
	
	bool lrs(int x) {
		return ls[fa[x]] == x;
	}
	
	void up(int x) {
		sum[x] = sum[ls[x]] + sum[rs[x]] + faksz[x] + 1;
	}
	
	void downt(int x) {
		swap(ls[x], rs[x]);
		lzyt[x] ^= 1;
	}
	
	void down(int x) {
		if (lzyt[x]) {
			if (ls[x]) downt(ls[x]);
			if (rs[x]) downt(rs[x]);
			lzyt[x] = 0;
		}
	}
	
	void down_line(int x) {
		if (nrt(x)) down_line(fa[x]);
		down(x);
	}
	
	void rotate(int x) {
		int y = fa[x];
		int z = fa[y];
		int b = (lrs(x) ? rs[x] : ls[x]);
		if (z && nrt(y)) (lrs(y) ? ls[z] : rs[z]) = x;
		if (lrs(x)) rs[x] = y, ls[y] = b;
			else ls[x] = y, rs[y] = b;
		fa[x] = z;
		fa[y] = x;
		if (b) fa[b] = y;
		up(y); up(x);
	}
	
	void Splay(int x) {
		down_line(x);
		while (nrt(x)) {
			if (nrt(fa[x])) {
				if (lrs(x) == lrs(fa[x])) rotate(fa[x]);
					else rotate(x);
			}
			rotate(x);
		}
	}
	
	void access(int x) {
		int lst = 0;
		for (; x; x = fa[x]) {
			Splay(x);
			
			faksz[x] += sum[rs[x]] - sum[lst];
			rs[x] = lst;
			up(x);
			lst = x;
		}
	}
	
	int find_root(int x) {
		access(x);
		Splay(x);
		while (down(x), ls[x])
			x = ls[x];
		Splay(x);
		return x;
	}
	
	void make_root(int x) {
		access(x);
		Splay(x);
		downt(x);
	}
	
	void link(int x, int y) {
		make_root(x);
		make_root(y);
		fa[x] = y;
		faksz[y] += sum[x];
		up(y);
	}
}T;

int main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	
	n = read(); m = read();
	
	for (int i = 1; i <= n; i++) T.up(i);
	
	while (m--) {
		op = read(); x = read();
		if (op == 1) T.make_root(x);
			else if (op == 2) {
				T.access(x);
				write(T.faksz[x] + 1); putchar('\n');
			}
			else if (op == 3) {
				rt = T.find_root(x);
				y = read();
				T.link(x, y);
				T.make_root(rt);
			}
	}
	
	return 0;
}