转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
动态树入门题，不需要维护任何信息。
我用的是splay，下标实现的lct。
#include <iostream>
#include <sstream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
using namespace std;
#define XINF INT_MAX
#define INF 0x3FFFFFFF
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;
#define MAXN 100010
int ch[MAXN][],key[MAXN],pre[MAXN],size[MAXN],ss[MAXN];
int rev[MAXN];
void push_down(int r){
if(!r)return;
if(rev[r]){
rev[ch[r][]]^=;
rev[ch[r][]]^=;
swap(ch[r][],ch[r][]);
rev[r]=;
}
}
void rotate(int x,int d){
int y=pre[x];
ch[y][!d]=ch[x][d];
if(ch[x][d])pre[ch[x][d]]=y;
pre[x]=pre[y];
if(ch[pre[y]][]==y)ch[pre[x]][]=x;
else if(ch[pre[y]][]==y)ch[pre[x]][]=x;
pre[y]=x;
ch[x][d]=y;
}
bool check(int x,int y){
return y&&(ch[y][]==x||ch[y][]==x);
}
void splay(int x){
push_down(x);
int y,z;
while(check(x,y=pre[x])){
if(check(y,z=pre[y])){
push_down(z);
push_down(y);
push_down(x);
int d=(y==ch[z][]);
if(x==ch[y][d]) {rotate(x,!d),rotate(x,d);}
else {rotate(y,d),rotate(x,d);}
}else{
push_down(y);
push_down(x);
rotate(x,ch[y][]==x);
break;
}
}
}
int access(int u){
int v=;
for(;u;u=pre[u]){
splay(u);
ch[u][]=v;
v=u;
}
//splay(u);
return v;
}
int getroot(int x){
for(x=access(x);push_down(x),ch[x][];x=ch[x][]);
return x;
}
void makeroot(int x){
rev[access(x)]^=;
splay(x);
}
void link(int x,int y){
makeroot(x);
pre[x]=y;
access(x);
}
void cut(int x,int y){
makeroot(x);
access(y);
splay(y);
pre[ch[y][]]=;
ch[y][]=;
}
void init(int n){
for(int i=;i<=n;i++)
ch[i][]=ch[i][]=pre[i]=;
}
void query(int x,int y){
int ra=getroot(x);
int rb=getroot(y);
if(ra==rb&&ra)printf("Yes\n");
else printf("No\n");
} int main()
{
ios::sync_with_stdio(false);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
init(n);
int x,y;
char a[];
for(int i=;i<m;i++){
scanf("%s%d%d",a,&x,&y);
if(a[]=='C')link(x,y);
else if(a[]=='D')cut(x,y);
else query(x,y);
}
}
return ;
}