题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2049
第二道LCT！
这题是模板题，写了一遍以后感觉对LCT的认识又加深了。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int const maxn=10005,maxm=200005; int n,m,c[maxn][3],rev[maxn],pre[maxn]; int rd() { int ret=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return ret*f; } void reverse(int x) { if(rev[x]) { rev[c[x][0]]^=1; rev[c[x][1]]^=1; swap(c[x][0],c[x][1]); rev[x]=0; } } bool isroot(int x) { return c[pre[x]][0]!=x && c[pre[x]][1]!=x; } void rotate(int x) { int y=pre[x],z=pre[y],d=(c[y][1]==x); if(!isroot(y))c[z][c[z][1]==y]=x; pre[x]=z; pre[y]=x; c[y][d]=c[x][!d]; pre[c[x][!d]]=y; c[x][!d]=y; } void splay(int x) { int sta[maxn],top; sta[top=1]=x; for(int p=x;!isroot(p);p=pre[p])sta[++top]=pre[p]; for(;top;top--)reverse(sta[top]); for(;!isroot(x);rotate(x)) { int y=pre[x],z=pre[y]; if(isroot(y))continue; ((c[y][1]==x)^(c[z][1]==y))?rotate(x):rotate(y); } } void access(int x) { for(int t=0;x;c[x][1]=t,t=x,x=pre[x]) splay(x); } void makeroot(int x) { access(x); splay(x); rev[x]^=1; } void link(int x,int y) { makeroot(x); pre[x]=y; // splay(x);////? } void query(int x,int y) { makeroot(x); access(y); splay(y); } void cut(int x,int y) { query(x,y); pre[x]=0; c[y][0]=0;//access(y) 后 y 为 x 右儿子 } int find(int x)//找到 x 所在树的根节点 { access(x); splay(x); int y=x; while(c[y][0])y=c[y][0]; return y; } int main() { n=rd(); m=rd(); char ch[10];int x,y; while(m--) { scanf("%s",&ch); x=rd(); y=rd(); if(ch[0]=='Q') { if(find(x)==find(y))printf("Yes "); else printf("No "); } if(ch[0]=='C')link(x,y); if(ch[0]=='D')cut(x,y); } return 0; }