HDU2475

【题意】给出N个正方形，有两种操作：MOVE x y：把x以及嵌套在x里面的所有盒子放进y内，如果y为0则放在地上；query x：查询x所在盒子最外面的那个盒子编号；

【分析】把盒子嵌套看成树，最外层的盒子就是树根，则有一篇森林，正好符合动态树的cut和link操作，只是在link的时候可以在同一个子树内移动，害我无数WA。另外是有根树，所以不能用原来的make_root操作的LCT，我这里用了很简洁的论文中说的原始的LCT，感觉常数很小。

【AC CODE】390ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10, MAXIN = 10000, MAXOUT = 10000;
char buf[MAXIN], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe) pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;
	do{ rnext(); if('-' == *ps) f = -1;} while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;
	do{ ans = (ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
inline void in_str(char *s)
{
	do{rnext();}while(!isalpha(*ps));
	do{*(s++) = *ps;rnext();}while(isalpha(*ps));
}
char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
inline void write(){ fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;}
inline void out_char(char c){ *(pout++) = c;if(pout == pend) write();}
inline void out_str(char *s)
{
	while(*s){ *(pout++) = *(s++); if(pout == pend) write(); }
}
template <class T>
inline void out_int(T x) {
	if(!x){ out_char('0');return;}
	if(x < 0) x = -x,out_char('-');
	int len = 0;
	while(x){ outtmp[len++] = x%10+48; x /= 10;}
	outtmp[len] = 0;
	for(int i = 0, j = len-1; i < j; i++,j--) swap(outtmp[i],outtmp[j]);
	out_str(outtmp);
}
int par[MAXN],ch[MAXN][2],fa[MAXN];

inline int chd(int u){return ch[fa[u]][1] == u;}
inline void setch(int f, int u, int d){ch[f][d] = u;fa[u] = f;}
inline void rot(int u)
{
	int d = chd(u), y = fa[u];
	setch(fa[y],u,chd(y));
	setch(y,ch[u][d^1],d);
	setch(u,y,d^1);
}
int find_sf(int u)
{
	while(fa[u]) u = fa[u];
	return u;
}
void splay(int u)
{
	int rt = find_sf(u);
	if(u == rt) return;
	par[u] = par[rt];par[rt] = 0;
	while(fa[u])
	{
		if(fa[fa[u]] && chd(u) == chd(fa[u])) rot(fa[u]);
		rot(u);
	}
}
void expose(int u)
{
	for(int la = 0,now = u;now;la = now,now = par[now])
	{
		splay(now);
		fa[ch[now][1]] = par[la] = 0;par[ch[now][1]] = now;
		setch(now,la,1);
	}
	splay(u);
}
void cut(int u)
{
	expose(u);
	par[ch[u][0]] = par[u] = fa[ch[u][0]] = 0;
	ch[u][0] = 0;
}
int find_root(int u)
{
	expose(u);
	while(ch[u][0]) u = ch[u][0];
	return u;
}
void link(int u, int v)//可以在同一个子树内移动
{
	if(!v)
	{
		cut(u);
		return;
	}
	expose(v);
	if(find_sf(u) == v) return;
	cut(u);par[u] = v;
}
void init()
{
	clc(par,0);
	clc(ch,0);
	clc(fa,0);
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,count = 0;
	while(in(n))
	{
		init();
		repe(i,1,n) in(par[i]);
		int q;
		in(q);
		if(count++) out_char('\n');
		char op[10];
		while(q--)
		{
			int x,y;
			in_str(op);in(x);
			if('M' == op[0])
			{
				in(y);
				link(x,y);
			}
			else out_int(find_root(x)),out_char('\n');
		}
	}
	write();
	return 0;
}