问：快要期末考了为什么不好好学习文化课呢？
答：学习文化课太无聊了而且没有前途。。。
问：那为什么要学这个诡异的蒜法呢？
答：因为窝splay找不到模板题刷了。。
【简介】
首先lct与树链剖分有着密切的关系。
树链剖分，即把一棵su剖出轻重链，然后用数据结构维护重链。
但是当树的形态改变时，原来的重链可能就不是最优的剖分方式了。
那么就需要用数据结构来维护重链。可以用splay，关键字为深度。
lct的核心操作Access，就是把root~x的所有边都变成重链。
由此窝萌阔以兹磁如下操作：
makeroot：将x变成根，只需要Access一下然后打个翻转标记就行。
link：加一条x->y的边，那么makeroot(x)，x的父亲记为y
cut：删除x->y的边，那么makeroot(x)，再将y旋到根，把左儿子断掉。
至于维护一些路径上的东西，只要用splay记录一下就阔以了。
void pushdown(int x){
int l=son[x][0],r=son[x][1];
if (rev[x]){
rev[l]^=1;rev[r]^=1;rev[x]=0;
swap(son[x][0],son[x][1]);
}
}
int isroot(int x){
return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
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){
top=0;q[++top]=x;
for (int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];
for (int i=top;i;i--)pushdown(q[i]);
while (!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (son[y][0]==x^son[z][0]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){
for (int t=0;x;t=x,x=fa[x]){
splay(x);
son[x][1]=t;
}
}
int find(int x){
access(x);
splay(x);
while (son[x][0])x=son[x][0];
return x;
}
void makeroot(int x){
access(x);splay(x);rev[x]^=1;
}
void cut(int x,int y){
makeroot(x);access(y);splay(y);
son[y][0]=fa[x]=0;
}
void link(int x,int y){
makeroot(x);fa[x]=y;
}
【例题】
Bzoj2049 果奔lct，维护一个link和cut就行了。
Bzoj2002 建树小学难度，然后用lct来维护树的深度。
Bzoj3282 果奔lct，link和cut的时候注意一下。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
int n,m,i,x,y,top;
int size[M],fa[M],son[M][2],rev[M],q[M];
void pushdown(int x){
int l=son[x][0],r=son[x][1];
if (rev[x]){
rev[l]^=1;rev[r]^=1;rev[x]=0;
swap(son[x][0],son[x][1]);
}
}
int isroot(int x){
return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
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){
top=0;q[++top]=x;
for (int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];
for (int i=top;i;i--)pushdown(q[i]);
while (!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (son[y][0]==x^son[z][0]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){
for (int t=0;x;t=x,x=fa[x]){
splay(x);
son[x][1]=t;
}
}
int find(int x){
access(x);
splay(x);
while (son[x][0])x=son[x][0];
return x;
}
void makeroot(int x){
access(x);splay(x);rev[x]^=1;
}
void cut(int x,int y){
makeroot(x);access(y);splay(y);
son[y][0]=fa[x]=0;
}
void link(int x,int y){
makeroot(x);fa[x]=y;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
char s[10];
scanf("%s",s);
scanf("%d%d",&x,&y);
if (s[0]=='C')link(x,y);
else if (s[0]=='D')cut(x,y);
else {if (find(x)==find(y))puts("Yes");else puts("No");}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000000;
int n,m,i,x,y,opt;
int fa[M],son[M][2],isroot[M],size[M];
void pushup(int x){
int l=son[x][0],r=son[x][1];
size[x]=size[l]+size[r]+1;
}
void rotate(int x){
int y=fa[x],z=fa[y],w=x==son[y][0];
son[y][!w]=son[x][w];fa[son[x][w]]=y;
son[x][w]=y;fa[y]=x;fa[x]=z;
if (!isroot[y])if (y==son[z][0])son[z][0]=x;else son[z][1]=x;
isroot[x]=isroot[y];isroot[y]=0;
pushup(y);pushup(x);
}
void splay(int x){while (!isroot[x])rotate(x);}
void access(int x){
int y;
splay(x);
while (fa[x]){
y=fa[x];
splay(y);
isroot[son[y][1]]=1;
isroot[x]=0;
son[y][1]=x;
pushup(y);
splay(x);
}
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d",&x);
if (i+x>n)fa[i]=n+1;else fa[i]=i+x;
}
scanf("%d",&m);
for (i=1;i<=n+1;i++)size[i]=isroot[i]=1;
for (i=1;i<=m;i++){
scanf("%d",&opt);
if (opt==1){
scanf("%d",&x);
x++;
access(x);
printf("%d\n",size[son[x][0]]);
}else{
scanf("%d%d",&x,&y);
x++;
splay(x);
fa[son[x][0]]=fa[x];
isroot[son[x][0]]=1;
son[x][0]=0;
pushup(x);
if (x+y>n)fa[x]=n+1;else fa[x]=x+y;
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=500010;
int n,m,i,opt,x,y,top;
int size[M],data[M],sum[M],rev[M],son[M][2],fa[M],q[M];
void pushdown(int x){
int l=son[x][0],r=son[x][1];
if (rev[x]){
rev[l]^=1,rev[r]^=1,rev[x]=0;
swap(son[x][0],son[x][1]);
}
}
int isroot(int x){
return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
void pushup(int x){
int l=son[x][0],r=son[x][1];
sum[x]=sum[l]^sum[r]^data[x];
}
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;
pushup(y);pushup(x);
}
void splay(int x){
top=0;q[++top]=x;
for (int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];
for (int i=top;i;i--)pushdown(q[i]);
while (!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (son[y][0]==x^son[z][0]==y)rotate(x);else rotate(y);
}
rotate(x);
}
}
void access(int x){
for (int t=0;x;t=x,x=fa[x]){
splay(x);
son[x][1]=t;
pushup(x);
}
}
int find(int x){
access(x);splay(x);
while (son[x][0])x=son[x][0];
return x;
}
void makeroot(int x){
access(x);splay(x);rev[x]^=1;
}
void cut(int x,int y){
makeroot(x);access(y);splay(y);
if (son[y][0]==x)son[y][0]=fa[x]=0;
}
void link(int x,int y){
makeroot(x);fa[x]=y;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)scanf("%d",&data[i]),sum[i]=data[i];
for (i=1;i<=m;i++){
scanf("%d",&opt);
if (opt==0){
scanf("%d%d",&x,&y);
makeroot(x);
//printf("%d\n",sum[x]);
access(y);
//printf("%d\n",sum[x]);
splay(y);
printf("%d\n",sum[y]);
}
if (opt==1){
scanf("%d%d",&x,&y);
if (find(x)!=find(y))link(x,y);
}
if (opt==2){
scanf("%d%d",&x,&y);
if (find(x)==find(y))cut(x,y);
}
if (opt==3){
scanf("%d%d",&x,&y);
access(x);
splay(x);
data[x]=y;
pushup(x);
}
}
}
