推荐：https://www.cnblogs.com/flashhu/p/8324551.html

分析

用来处理有删边但没有子树操作的问题

模板

inline bool nrt(int x) { //判断x是否为splay中的根，认父不认子
    return c[f[x]][0]==x||c[f[x]][1]==x;
}

void rotate(int x) {
    int y=f[x],z=f[y],k=c[y][1]==x;
    if(nrt(y)) c[z][c[z][1]==y]=x; f[x]=z;
    if(c[x][!k]) f[c[x][!k]]=y; c[y][k]=c[x][!k];
    c[x][!k]=y,f[y]=x;
    up(y);
}

void splay(int x) {
    int y=x,z=0;
    st[++z]=x;
    while(nrt(y)) st[++z]=f[y],y=f[y];
    while(z) down(st[z--]); 
    while(nrt(x)) {
        int y=f[x],z=f[y];
        if(nrt(y)) {
            rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
        }
        rotate(x);
    }
    up(x);
}

access：打通x到根的道路，splay中的键值是深度

void access(int x) {
    for(int y=0;x;y=x,x=f[x]) {
        splay(x),c[x][1]=y,f[y]=x,up(x);
    }
}

makeroot：将x变成根

inline void pushr(int x) {
    swap(c[x][0],c[x][1]);
    rev[x]^=1;
}

void makert(int x) {
    access(x),splay(x);
    pushr(x);
}

split：将x，y路径提到一个splay中，以y为根

void split(int x,int y) {
    makert(x),access(y),splay(y);
}

*findroot：寻找x的根（树上）

int findrt(int x) {
    access(x),splay(x);
    for(;c[x][0];x=c[x][0]) down(x);
    splay(x); //保证时间复杂度
    return x;
}

link：连接

void link(int x,int y) {
    makert(x);
    *if(findrt(y)==x) return;
    f[x]=y;
}

cut：删除

void cut(int x,int y) {
    makert(x),access(y),splay(y);
    *if(c[y][0]!=x||c[x][1]||f[x]!=y) return;
    f[x]=0,c[y][0]=0; up(y);
}

LCT板子

原文：https://www.cnblogs.com/wsfwsf/p/14635641.html