LCT要保证时时刻刻都是一棵树（图中自始至终无环出现）
bzoj2049
无根树LCT（Link和Cut的时候都要make_root，需要lazy-tag标记）
只维护连通性，父子关系不重要
维护fa(x) lc(x) rc(x) tag(x)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000000
using namespace std;
int n, m;
struct node
{
	int fa, lc, rc, tag;
	#define fa(x) tr[x].fa
	#define lc(x) tr[x].lc
	#define rc(x) tr[x].rc
	#define tag(x) tr[x].tag
}tr[N];

inline int is_root(int x)
{
	if(!fa(x)) return 1;
	else return x != lc(fa(x)) && x != rc(fa(x));
}

inline int which(int x)
{
	return x == rc(fa(x));
}

inline void Rotate(int x)
{
	int y = fa(x);
	int z = fa(y);
	int s = x == lc(y) ? rc(x) : lc(x);
	
	if(!is_root(y)) (y == lc(z) ? lc(z) : rc(z)) = x;
	
	if(s) fa(s) = y;
	fa(y) = x;
	fa(x) = z;
	
	if(x == lc(y)) rc(x) = y, lc(y) = s;
	else 		   lc(x) = y, rc(y) = s;
}

inline void pushdown(int x)
{
	if(tag(x))
	{
		tag(x) = 0;
		swap(lc(x), rc(x));
		if(lc(x)) tag(lc(x)) ^= 1;
		if(rc(x)) tag(rc(x)) ^= 1;
	}
}

int temp[N];
inline void splay(int x)
{
	int cnt = 1;
	temp[1] = x;
	for(int z = x; !is_root(z); z = fa(z))
		temp[++cnt] = fa(z);
	
	for(int i=cnt; i; --i) pushdown(temp[i]);
	
	while(!is_root(x))
	{
		if(!is_root(fa(x)))
		{
			if(which(x) == which(fa(x))) Rotate(fa(x));
			else Rotate(x);
		}
		Rotate(x);
	}
}

inline void Access(int x)
{
	int y = 0;
	while(x)
	{
		splay(x);
		rc(x) = y;
		y = x;
		x = fa(x);
	}
}

inline int Find_root(int x)
{
	Access(x);
	splay(x);
	while(lc(x)) x = lc(x);
	return x;
}

inline void Make_root(int x)
{
	Access(x);
	splay(x);
	tag(x) ^= 1;
}

inline void Link(int x, int y)
{
	Make_root(x);
	fa(x) = y;
}

inline void Cut(int x, int y)
{
	Make_root(x);
	Access(y);
	splay(y);
	lc(y) = 0;
	fa(x) = 0;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i=1, x, y; i<=m; ++i)
	{
		char opt[100];
		scanf("%s%d%d", opt, &x, &y);
		if(opt[0] == 'Q') printf(Find_root(x) == Find_root(y) ? "Yes\n" : "No\n");
		else if(opt[0] == 'C') Link(x, y);
		else Cut(x, y);
	}
}

hdu2475 有根树LCT
父子关系表示箱子的包含关系，所以父子关系不能随便颠倒，所以不能用make_root，不用make_root的话，也不用打lazy_tag标记了。
Cut里面只传一个参数x，表示减掉x和x父亲的连边
维护fa(x) lc(x) rc(x)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100000
using namespace std;
int n, m;
struct node
{
	int fa, lc, rc;
	#define fa(x) tr[x].fa
	#define lc(x) tr[x].lc
	#define rc(x) tr[x].rc
}tr[N];

inline int is_root(int x)
{
	if(!fa(x)) return 1;
	else return x != lc(fa(x)) && x != rc(fa(x));
}

inline int which(int x)
{
	return x == rc(fa(x));
}

inline void Rotate(int x)
{
	int y = fa(x);
	int z = fa(y);
	int s = x == lc(y) ? rc(x) : lc(x);
	
	if(!is_root(y)) (y == lc(z) ? lc(z) : rc(z)) = x;
	
	if(s) fa(s) = y;
	fa(y) = x;
	fa(x) = z;
	
	if(x == lc(y)) rc(x) = y, lc(y) = s;
	else 		   lc(x) = y, rc(y) = s;
}

int temp[N];
inline void splay(int x)
{
	int cnt = 1;
	temp[1] = x;
	for(int z = x; !is_root(z); z = fa(z))
		temp[++cnt] = fa(z);
	
//	for(int i=cnt; i; --i) pushdown(temp[i]);
	
	while(!is_root(x))
	{
		if(!is_root(fa(x)))
		{
			if(which(x) == which(fa(x))) Rotate(fa(x));
			else Rotate(x);
		}
		Rotate(x);
	}
}

inline void Access(int x)
{
	int y = 0;
	while(x)
	{
		splay(x);
		rc(x) = y;
		y = x;
		x = fa(x);
	}
}

inline int Find_root(int x)
{
	Access(x);
	splay(x);
	while(lc(x)) x = lc(x);
	return x;
}

inline void Cut(int x) //减掉x和x父亲的连边 
{
	Access(x);
	splay(x);
	fa(lc(x)) = 0;
	lc(x) = 0;
}

inline void Link(int x, int y) 
{
	if(x == y) return;
	if(!y) Cut(x);
	else
	{
		Access(y);
		splay(y);
		int z = x;
		while(!is_root(z)) z = fa(z); // 只能在一条重链(一棵splay内)跳 
		if(z == y) return;
		Cut(x);
		fa(x) = y;
	}
}

int main()
{
	int n, flag = 0;
	while(scanf("%d", &n) == 1)
	{
		if(flag) printf("\n");
		flag = 1;
		for(int i=1; i<=n; ++i) lc(i) = rc(i) = 0; 
		for(int i=1; i<=n; ++i) scanf("%d", &fa(i));
		
		int q;
		scanf("%d", &q);
		while(q--)
		{
			char c[10];
			int x, y;
			scanf("%s%d", c, &x);
			if(c[0] == 'M')
			{
				scanf("%d", &y);
				Link(x, y);
			}
			else printf("%d\n", Find_root(x));
			//for(int i=1; i<=n; ++i) printf("%d %d %d\n", fa(i), lc(i), rc(i));
		}
	}
}