Link-cut Tree

这可能是我第一次学数据结构如此绝望

链剖分

重链剖分

使用静态数据结构维护

实链剖分（LCT）

使用splay维护

对每个节点，选择一个儿子作为实边，其他为虚边
实链用splay维护

虚边认父不认子，连接两个splay

长链剖分

查询修改链上信息

随意换根

动态维护连通性

LCT核心操作

access(x)

从指定节点到根节点，自下往上，打通根节点到指定节点的实链，是的一条从根开始指定节点结束的splay出现

splay旋转路径上对于有实变得点，让他变虚，对于x路径上的点变重。把要改虚的边用旋转去掉。

splay是二叉树，在splay上进行操作

• 转到根 splay
• 换儿子
• 更新信息
• 当前操作节点切换到轻边所指的父节点

splay按深度排序，只会在右边，不会在左边

以深度为关键信息的BST

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

makeroot(x)

将 x 变成原树的根

access(x)

splay(x)

反转整个splay，所有点的深度倒过来

x没有左子树

void rev(int x){
    swap(c[x][0],c[x][1]);
    r[x] ^= 1;
}
void makeroot(int x){
    access(x);
    splay(x);
    rev(x);
}

findroot(x)

access(x)

x与根在同一个splay中

splay(x)后根在x的最左子节点

要pushdown()

void pushdown(x){
    if(r[x]){
        if(c[x][0])rev(c[x][0]);
        if(c[x][1])rev(c[x][1]);
        r[x]=0;
    }
}
int findroot(int x){
    access(x);
    splay(x);
    while(c[x][0]){
        pushdown(x);
        x=c[x][0];
    }
    splay(x);
    return x;
}

split(x,y)

将x到y的路径放到一个单独的splay中

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

link 连一条x-y的边

bool link(int x,int y){
    makeroot(x);
    if(findroot(y)==x)return false;
    f[x]=y;
    return true;
}
void link(int x,int y){
    makeroot(x);
    fa[x]=y;
}

cut

将x-y边断开

void cut(int x,int y){
    split(x,y);
    f[x]=c[y][0]=0;//做了access操作
    pushup(y);
}
bool cut(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)return false;
    if(f[y]!=x)return false;
    if(c[y][0])return false;
    f[y]=c[x][1]=0;
    pushup(x);//具体题目具体分析
    return true;
}

时间复杂度

势能分析，单次 access(x) 操作 \(O(\log n)\)

判断它是不是当前的根

//不会splay怎么办，学，资源很多

splay修改l，r，但是提根要提l-1，r+1