又一道LCT模板题。
如何找是不是在同一棵树上？只要找深度最小的点是不是相同的点即可。
也就是splay最左边的那个点。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 10050 #define maxe 20050 using namespace std; int n,m,fath[maxv],size[maxv],tree[maxv][3],x,y,rev[maxv]; int stack[maxv],top=0; char s[20]; bool isroot(int x) { return tree[fath[x]][1]!=x&&tree[fath[x]][2]!=x; } void pushdown(int x) { if (rev[x]) { int ls=tree[x][1],rs=tree[x][2]; rev[ls]^=1;rev[rs]^=1;rev[x]=0; swap(tree[x][1],tree[x][2]); } } void pushup(int x) { int ls=tree[x][1],rs=tree[x][2]; size[x]=size[ls]+size[rs]+1; } void rotate(int x) { int y=fath[x],z=fath[y],l,r; if (tree[y][1]==x) l=1;else l=2; r=3-l; if (!isroot(y)) { if (tree[z][1]==y) tree[z][1]=x; else tree[z][2]=x; } fath[x]=z;fath[y]=x;fath[tree[x][r]]=y; tree[y][l]=tree[x][r];tree[x][r]=y; pushup(y);pushup(x); } void splay(int x) { top=0; stack[++top]=x; for (int i=x;!isroot(i);i=fath[i]) stack[++top]=fath[i]; for (int i=top;i>=1;i--) pushdown(stack[i]); while (!isroot(x)) { int y=fath[x],z=fath[y]; if (!isroot(y)) { if ((tree[y][1]==x)^(tree[z][1]==y)) rotate(x); else rotate(y); } rotate(x); } } void access(int x) { int regis=0; while (x) { splay(x); tree[x][2]=regis; regis=x;x=fath[x]; } } void makeroot(int x) { access(x); splay(x); rev[x]^=1; } void link() { scanf("%d%d",&x,&y); makeroot(x); fath[x]=y; splay(x); } void cut() { scanf("%d%d",&x,&y); makeroot(x);access(y); splay(y);tree[y][1]=0;fath[x]=0; } int find(int x) { access(x);splay(x); int y=x; while (tree[y][1]) y=tree[y][1]; return y; } void query() { scanf("%d%d",&x,&y); int u=find(x),v=find(y); if (u==v) printf("Yes "); else printf("No "); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) size[i]=1; for (int i=1;i<=m;i++) { scanf("%s",s); if (s[0]=='C') link(); else if (s[0]=='D') cut(); else if (s[0]=='Q') query(); } return 0; }