BZOJ2049

【分析】这题是无根树的LCT的cut和link操作，有根树LCT不能使用make_root()操作(因为给出的边是有向的)，而无根树的LCT则必须使用make_root()来确保边的方向；其他都差不多，而无根树是没法确定LCA的，总之无根树LCT和有根树的LCT是不一样的。

【AC CODE】1436ms

#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 = 10000+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],fz[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 rev(int u)
{
	swap(ch[u][0],ch[u][1]);
	fz[u] ^= 1;
}
inline void push_down(int u)
{
	if(fz[u])
	{
		rev(ch[u][0]),rev(ch[u][1]);
		fz[u] = 0;
	}
}
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 dfs_down(int u)
{
	if(fa[u]) dfs_down(fa[u]);
	push_down(u);
}
void splay(int u)
{
	dfs_down(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);
}
int find_root(int u)
{
	expose(u);
	while(ch[u][0]) u = ch[u][0];
	return u;
}
void make_root(int u)
{
	expose(u);
	rev(u);
}
void cut(int u)
{
	expose(u);
	par[ch[u][0]] = par[u];
	par[ch[u][0]] = par[u] = fa[ch[u][0]] = 0;
	ch[u][0] = 0;
}
void cut(int u, int v)
{
	make_root(u);
	cut(v);
}
void link(int u, int v)
{
	if(u == v || find_root(u) == find_root(v)) return;
	make_root(u);
	par[u] = v;
}
void init()
{
	clc(par,0);
	clc(ch,0);
	clc(fa,0);
	clc(fz,0);
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	while(in(n))
	{
		init();
		int q;
		in(q);
		char op[10];
		while(q--)
		{
			int x,y;
			in_str(op);in(x);in(y);
			if('C' == op[0])
			{
				link(x,y);
			}
			else if('D' == op[0])
				cut(x,y);
			else
			{
				if(find_root(x) == find_root(y)) out_str("Yes\n");
				else out_str("No\n");
			}
		}
	}
	write();
	return 0;
}