[bzoj 2049] [Sdoi2008]Cave 洞穴勘测

维护一片森林, 支持Connect, Destroy和查询连通性. 点数n≤10000, 操作数m≤200000. 最近写的第一道LCT.

#include <bits/stdc++.h>

using namespace std;
const int MAX_N = 1e4;

struct Node {
	Node* ch[2], * fa;
	bool rev;
	int t;

	Node();

	void setf(int t1, Node* f)
	{
		t = t1;
		fa = f;
		t >= 0 ? f->ch[t] = this : 0;
	}

	void reverse()
	{
		rev = !rev;
		swap(ch[0], ch[1]);
		ch[0]->t = 0;
		ch[1]->t = 1;
	}

	void down()
	{
		if (rev) {
			ch[0]->reverse();
			ch[1]->reverse();
			rev = false;
		}
	}
} nodes[MAX_N + 1], * nil = nodes;

Node::Node(): fa(nil), rev(false), t(-1) { ch[0] = ch[1] = nil; }

inline void rot(Node* y)
{
	Node* x = y->fa;
	int t = y->t;
	y->setf(x->t, x->fa);
	y->ch[t^1]->setf(t, x);
	x->setf(t^1, y);
}

void splay(Node* x)
{
	Node* y;
	int top = 0;
	static Node* S[MAX_N];

	for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
	for (y->down(); top; S[--top]->down()) ;

	while (x->t >= 0) {
		if ((y = x->fa)->t >= 0)
			rot(x->t ^ y->t ? x : y);
		rot(x);
	}
}

inline void access(Node* x)
{
	for (Node* y = nil; x != nil; y = x, x = x->fa) {
		splay(x);
		x->ch[1]->t = -1;
		y->setf(1, x);
	}
}

inline void make_root(Node* x)
{
	access(x);
	splay(x);
	x->reverse();
}

inline void link(Node* x, Node* y)
{
	make_root(x);
	x->setf(-1, y);
}

inline void cut(Node* x, Node* y)
{
	make_root(y);
	access(x);
	splay(x);
	x->ch[0] = y->fa = nil;
	y->t = -1;
}

inline Node* find_root(Node* x)
{
	access(x);
	splay(x);
	while (x->ch[0] != nil) {
		x = x->ch[0];
		x->down();
	}
	return x;
}

int main()
{
	int n, m, u, v;
	char s[8];

	scanf("%d%d", &n, &m);
	while (m--) {
		scanf("%s%d%d", s, &u, &v);
		Node* x = nodes + u, * y = nodes + v;
		switch (s[0]) {
		case 'Q':
			puts(find_root(x) == find_root(y) ? "Yes" : "No"); break;
		case 'C':
			link(x, y); break;
		default:
			cut(x, y);
		}
	}
	return 0;
}