例题：BZOJ2049 [Sdoi2008]Cave 洞穴勘测
首先，LCT中的splay是按深度为key值维护的，一颗树的形态是通过维护一颗splay中点的中序遍历和一颗splay根的fa连接而成。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int n,m,fa[10010],son[10010][2],rev[10010],top,Stack[10010]; bool isRoot(int x)//判断x是否为根 { return son[fa[x]][0]!=x&&son[fa[x]][1]!=x; } void pushdown(int x) { if (rev[x]) { if (son[x][0]) rev[son[x][0]]^=1; if (son[x][1]) rev[son[x][1]]^=1; swap(son[x][0],son[x][1]); rev[x]=0; } } void Rotate(int x) { int y=fa[x],z=fa[y],l,r; if (son[y][0]==x) l=0;else l=1; r=l^1; if (!isRoot(y)) { if (son[z][0]==y) son[z][0]=x;else son[z][1]=x; } fa[x]=z;fa[y]=x;fa[son[x][r]]=y; son[y][l]=son[x][r];son[x][r]=y; } void splay(int x)//和普通splay大致一样 { top=0;Stack[++top]=x; for (int i=x;!isRoot(i);i=fa[i]) Stack[++top]=fa[i]; for (;top;top--) pushdown(Stack[top]); while (!isRoot(x))//因为不是记录root，所以直接判断是否为根 { int y=fa[x],z=fa[y]; if (!isRoot(y)) { if ((son[z][0]==y)^(son[y][0]==x)) Rotate(x); else Rotate(y); } Rotate(x); } } void access(int x)//LCT中十分重要的操作，将Root->x所有的边都变为实边，即Root->x路径上所以的点都在同一颗splay中维护。 { for (int i=0;x;i=x,x=fa[x]) { splay(x);//先将x在其所在的splay中转到根 son[x][1]=i;//然后把下一层要连上来的连在右边，因为深度比当前x大， //并且若原本son[x][1]有值，那么就相当于断掉了。 } } int GetRoot(int x)//得到x所在树的根 { access(x);//先将Root->x变为实边 splay(x);//此时Root和x在同一颗splay中，这颗splay的点中x深度最深，Root的深度最浅。 while (son[x][0]) x=son[x][0];//Root的深度最浅，所以Root一定在最左边。 return x; } void MakeRoot(int x) { access(x);//将Root->x变为实边 splay(x);//将x转到splay的根处 rev[x]^=1;//注解见代码后的图片 } void link(int x,int y) { MakeRoot(x); fa[x]=y;//将x,y连起来 } void cut(int x,int y) { MakeRoot(x); access(y); splay(y); son[y][0]=0; fa[x]=0;//将x,y断开 } int main() { scanf("%d%d",&n,&m); while (m--) { char s[10];int x,y; scanf("%s%d%d",s,&x,&y); if (s[0]=='Q') { if (GetRoot(x)==GetRoot(y)) puts("Yes");else puts("No");} if (s[0]=='C') link(x,y); if (s[0]=='D') cut(x,y); } } |
