LCT（Link-Cut Tree） 总结（概念篇）

算法/数据结构总结

先膜一波HlashHu巨佬

概念与基本性质

首先我们得知道链剖分的意义，将一棵树剖成若干条链，以此来优化链上操作的时间复杂度。
链剖分主要有重链剖分，实链剖分以及长链剖分。
其中重链剖分与实链剖分比较常用，我们平时用的树剖就是重链剖分。
而 LCT 则是基于实链剖分来实现。

实链剖分

实链剖分即将一部分树边定义为实边，剩下的边即为虚边。
对于每一个节点，在连接它与它的儿子节点的边中只会有一条实边，其余的均为虚边。
由实边构成的链就叫实链。
但边的虚实是可以动态变化的，所以不能用线段树之类的偏静态数据结构来维护，需要更加灵活的 Splay 来维护每一条实链。
不会 Splay 的话可以到巨佬自为风月马前卒的博客详解一，详解二学习。
于是，基于优秀的实链剖分，以 Splay 为基础的 LCT(Link-Cut Tree) 出现了。
一般来说 LCT 维护的是一个森林，基于强大的实链剖分，LCT 资瓷更优(qi)秀(pa)的操作。

• 查询，修改一条链的信息（链剖分都行）。
• 修改原树的根（这个倒是不一样）。
• 动态连边加边。
• 动态维护连通性（当可撤销并查集用）。

但 LCT 并不能资瓷子树操作，所以当题目中有子树操作时还是得乖乖写树剖。

基本性质

哪个数据结构没有点性质呢。
在 LCT 中，每一棵 Splay 维护一条实链，Splay 以节点深度为键值，保持它的平衡。
每一个节点都包含且仅包含在一棵 Splay 中。
每一条实边都对应某一棵 Splay 的一条边，虚边则由一棵 Splay 指向另一棵 Splay 的一个节点（Splay 中深度最小的节点在原树中的父亲节点）。
对于实边，由于它们就是 Splay 中的边，所以只要用普通的 Splay 的记边方法就行了，但对于虚边，单个节点没有那么多位置来存虚边指向的儿子节点，所以直接抛弃，只记录儿子节点的父亲节点（认父不认子）即可。

基本操作

首先，我们需要一个判断某一节点是否是其所在的 Splay 中的根节点，原理很简单，应为对于一棵 Splay 的根节点来说它指向的父亲节点所指向的两个儿子节点是不指向它的，因为它们不在同一个 Splay 中。

inline bool isroot(int x){
    return (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x);
}

Splay 部分

这个不多讲，只要你会 Splay，那么这里需要资瓷的两个操作就不会有问题，只是有点不一样。

inline void rotate(int x){
    int y=fa[x],z=fa[y],k=(ch[y][1]==x);
    if(!isroot(y)) ch[z][ch[z][1]==y]=x;//防止将不是该 Splay 中的节点的儿子指向 x
    fa[x]=z;
    ch[y][k]=ch[x][k^1];
    if(ch[x][k^1]) fa[ch[x][k^1]]=y;//防止x节点没有k^1这个节点导致将0节点的父亲指向y节点
    ch[x][k^1]=y;
    fa[y]=x;
    pushup(y),pushup(x);
}
inline void splay(int x){
    int y=x,top=0;
    stk[++top]=y;
    while(!isroot(y)) stk[++top]=y=fa[y];//提前下放标记，一般情况下都要写，因为后续的基本操作会有翻转标记
    while(top) pushdown(stk[top--]);//pushdown(x) 后面会有
    while(!isroot(x)){
        y=fa[x];
        if(!isroot(y))//防止把节点旋转到Splay外
            rotate((ch[y][1]==x)^(ch[fa[y]][1]==y)?x:y);
        rotate(x);
    }
}

$access(x)$

它是 LCT 的核心操作，基本每一个操作都直接或间接地调用了 $access(x)$。
它的作用是将 $x$ 节点到原树根节点的路径变成一条实链，以此来方便执行其他操作。
$access(x)$ 的大致流程是这样的：

• 首先将当前节点 $splay()$ 一下，让当前节点跳到所在的 Splay 的根。
• 然后把上一次记录下来的 $y$ 节点设为当前节点的右儿子（一开始 $y$ 默认为 $0$）（因为 $y$ 节点的蛇深度大于当前节点，所以是右儿子）。
• 接着更新当前节点维护的值。
• 再将 $y$ 记录为当前节点编号，接着当前节点跳到它的父亲节点。
• 循环以上操作直至处理完根节点，因为只有根节点的父亲指针是指向 $0$ 节点的，所以只需要当前节点是 $0$ 节点时退出循环即可。

由于笔者画画技术很烂所以自行想象一下吧。

inline void access(int x){
    for(int y=0;x;y=x,x=fa[x])
        splay(x),ch[x][1]=y,update(x);//由于多了一个儿子，所以要更新当前节点的信息
}

$makeroot(x)$

这个函数便基于 $access(x)$，他可以将 $x$ 所在的原树的根换成 $x$ 来进行维护。
首先 $access(x)$ 打通 $x$ 与原树的根之间的路径，此时 $x$ 就是这个 Splay 中深度最大的点，因为 $access(x)$ 打通的路径是以 $x$ 为一个端点，以根为另一个端点的链。
这条链上的点除了 $x$ 点，其他点的深度自然大于 $x$ 的深度。
又因为 LCT 中的 Splay 是以深度为键值的，所以此时 $x$ 是没有右儿子的，毕竟这一个 Splay 中没有比 $x$ 深度更大的点了。
那么，我们可以将这一个 Splay 进行翻转，让左子树的节点全部到右边去，此时 $x$ 就成了原树的根。

inline void reverse(int x){
    swap(ch[x][0],ch[x][1]);tag[x]^=1;//标准的区间翻转
}
inline void makeroot(int x){
    access(x);splay(x);reverse(x);
}

既然有了标记，那么自然少不了 pushdown(x)，这里的 pushdown(x) 不仅用来下传翻转标记。如果题目要用到，也需要下传加法、乘法等其他标记。
总之，标记都在这下传。

inline void pushdown(int x){
    if(tag[x]){
        if(ch[x][0]) reverse(ch[x][0]);
        if(ch[x][1]) reverse(ch[x][1]);
        tag[x]=0;
    }
}

$findroot(x)$

这个函数用于查找 $x$ 所在原树的根节点，一般用来判断两点连通性，也有用来干其他事的，不过很少。
原理很简单,先 $access(x)$ 方便操作，再 $splay(x)$ 把 $x$ 给提上来，由于根节点的深度一定小于所有其他点，所以只需要一直往左儿子跳，直到没有左儿子为止。
由于常数问题，如果总用 $fidnroot(x)$ 容易被一些毒瘤题卡掉，有句话说的好。

珍爱生命，远离 $findroot()$。

不过该用的时候还是得用

inline int findroot(int x){
    access(x);splay(x);
    while(ch[x][0]) pushdown(x),x=ch[x][0];
    splay(x);
    return x;
}

$split(x,y)$

有了 $makeroot()$，我们便可以随意访问树上的任意一条链了。
$split(x,y)$ 函数的作用便是从树中提取出 $x-y$ 这一条链，方便进行链上查询与修改。
具体流程很简单，首先 $makeroot(x)$ 再 $access(y)$，此时 $x$ 与 $y$ 之间的路径便被提取了出来，但此时 $x$ 的信息并不能用作答案，需要 $splay(y)$ 来手收集信息。

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

$link(x,y)$

既然是动态树，自然少不了动态加边，顾名思义，$link(x,y)$ 就是新建一条连接 $x$ 与 $y$ 的边。
原理很简单，不多讲。

inline void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x) fa[x]=y;//如果题目明确指出，保证x与y不在同一个连通块中可以不进行联通性判断
}

$cut(x,y)$

有连边就有删边，$cut(x,y)$ 用于断开连接 $x$ 与 $y$ 的边。
当 $split(x,y)$ 之后，$x$ 一定是 $y$ 的右儿子，直接断开即可。

inline void cut(int x,int y){
    split(x,y);
    fa[x]=ch[y][0]=0;
    pushup(x);
}

但如果要判断合法性就得换一种写法，先 $makeroot(x)$，然后 $findroot(y)$ 在判断连通性的同时打通了 $x-y$ 这条路径。
在 $findroot(y)$ 变成了 Splay 的根，此时如果 $x$ 与 $y$ 有直接连边的话，$y$ 在 Splay 中的左儿子就是 $x$，现在双向断开这一条边就行。

inline void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&fa[y]==x&&!ch[y][0])
        fa[y]=ch[x][1]=0,pushup(x);
}

End

通常情况下，LCT 的板子就够用了，但在做题时还是要灵活变通，有些题目 Splay 的操作会需要改很多。
最后，对于那些没有子树操作的树剖题可以拿来练手，不过考试时还是乖乖写树剖好些，毕竟在有些题目中 LCT 的常数实在是太优秀了。

板题

P3690 【模板】动态树（Link Cut Tree）
这道题 LCT 的基本操作都有了，很好的练手题。
建议多练板子，最好是能一遍过。

#include<iostream>
using namespace std;
const int N(1e5+5);
int n,m;
int fa[N],ch[N][2],val[N],stk[N],sum[N];
bool tag[N];
inline bool isroot(int x){
    return (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x);
}
inline void pushup(int x){
    sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^val[x];
}
inline void reverse(int x){
    swap(ch[x][0],ch[x][1]);tag[x]^=1;
}
inline void pushdown(int x){
    if(tag[x]){
        if(ch[x][0]) reverse(ch[x][0]);
        if(ch[x][1]) reverse(ch[x][1]);
        tag[x]=0;
    }
}
inline void rotate(int x){
    int y=fa[x],z=fa[y],k=(ch[y][1]==x);
    if(!isroot(y)) ch[z][ch[z][1]==y]=x;
    fa[x]=z;
    ch[y][k]=ch[x][k^1];
    if(ch[x][k^1]) fa[ch[x][k^1]]=y;
    ch[x][k^1]=y;
    fa[y]=x;
    pushup(y),pushup(x);
}
inline void splay(int x){
    int y=x,top=0;
    stk[++top]=y;
    while(!isroot(y)) stk[++top]=y=fa[y];
    while(top) pushdown(stk[top--]);
    while(!isroot(x)){
        y=fa[x];
        if(!isroot(y))
            rotate((ch[y][1]==x)^(ch[fa[y]][1]==y)?x:y);
        rotate(x);
    }
}
inline void access(int x){
    for(int y=0;x;y=x,x=fa[x])
        splay(x),ch[x][1]=y,pushup(x);
}
inline void makeroot(int x){
    access(x);splay(x);reverse(x);
}
inline int findroot(int x){
    access(x);splay(x);
    while(ch[x][0]) pushdown(x),x=ch[x][0];
    splay(x);
    return x;
}
inline void split(int x,int y){
    makeroot(x);
    access(y);splay(y);
}
inline void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x) fa[x]=y;
}
inline void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&fa[y]==x&&!ch[y][0])
        fa[y]=ch[x][1]=0,pushup(x);
}
int main(){
    #ifdef ytxy
    freopen("in.txt","r",stdin);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>val[i];
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==0) split(x,y),cout<<sum[y]<<'\n';//split(x,y)最后是splay(y)收集答案，所以答案是记录在节点y上的
        else if(op==1) link(x,y);
        else if(op==2) cut(x,y);
        else if(op==3) splay(x),val[x]=y;//在每次查询都会split(x,y)顺便就更新节点信息，所以这里不用更新
    }
}