是什么

Link-Cut-Tree
一般称作 LCT/虚实链剖分
ps： LCT 不能称作 动态树，动态树 指的是一类问题。
由著名巨佬 Tarjan 发明（对，又是他）
用于解决动态的树上路径/子树问题（统称为动态树问题）
对于普通的树上问题，比如：

给定一颗 \(n\) 个节点的树，每个节点均有权值，需要维护三个操作：
1.查询 \(u\) 到 \(v\) 路径上的权值和
2.查询以 \(u\) 为根的子树的权值和
3.将 \(u\) 点的权值修改为 \(val\)

那么这是一道很板的 熟练剖粪 树链剖分题
但假如我们还需要维护两个操作：

4.将 \(u,v\) 这条边断开（如果有边的话）
5.将 \(u,v\) 连接起来（若 \(u,v\) 不在同一连通块内）

那么现在，普通的树剖就没有办法解决了
这时候，我们就需要用到 LCT

怎么做

变量声明

\(root\) 表示树的根
\(tot\) 表示当前树的节点个数
\(val_{i}\) 表示 \(i\) 节点的权值
\(son_{i,0}\) 表示 \(i\) 节点的左儿子
\(son_{i,1}\) 表示 \(i\) 节点的右儿子
\(fa_{i}\) 表示 \(i\) 节点的父亲
\(tag_{i}\) 表示 \(i\) 节点的翻转标记
\(cnt_{i}\) 表示 \(i\) 节点存储的数量（同样的值放在同一个节点）
\(siz_{i}\) 表示以 \(i\) 节点为根的子树大小

先将 LCT 模板题放在 这里
其实 LCT 的码量并不算太大，但是就比较难理解

前置芝士：二叉搜索树，Splay

二叉搜索树

我们在对一个序列进行各种操作的时候，
可能会遇见让你插入某个数，删除某个数，还需要让你随时都保证有序，
假如我们对一个普通的数组这样操作的话，如果从中间插入和删除之类的，需要用到 \(O(n)\) 的时间来维护序列的有序，
这样显然无法接受，我们需要优化时间复杂度。
考虑将序列转移到一颗二叉树上。

输出

我们让二叉树的中序遍历的结果，就是原先的序列。

那么怎么维护有序？假设我们需要维护单调递增的序列，对于每个节点 \(i\) 都满足 \(val_{son_{i,0}} < val_{i} < val_{son_{i,1}}\) 即可。

这样的话，经过中序遍历后得到的结果，就是单调递增的原序列了。

插入

设插入的值为 \(v\)。
根据前面所讲的输出方式，我们在插入的时候，使二叉树依然满足性质即可。
最开始令 \(pos \gets root\)。
（ps：\(a \gets b\) 表示将 \(b\) 的值赋给 \(a\)）
一直重复下面这个式子，直到 \(pos=0\)。

\[ \left\{\begin{matrix} pos \gets son_{pos,0}(v<val_{pos})\\ pos \gets son_{pos,1}(v>val_{pos}) \end{matrix}\right. \]

\(pos=0\) 后，我们就可以将 \(tot \gets tot+1\) 并将新的这个权值 \(v\) 赋给 \(val_{tot}\)
记住插入后要更新 \(fa_{tot}\) 和 \(son_{fa_{tot},0/1}\)
这样插入操作就完成了！
代码如下：

void insert(int v){
    int pos=root;
    int f=0;
    while(true){
        if(pos==0){
            val[++tot]=v;
            fa[tot]=f;
            if(f!=0) son[f][v>val[f]]=v;
            break;
        }
        fa=pos;
        if(v==val[pos]){
            cnt[pos]++;
            break;
        }
        pos=son[pos][v>val[pos]];
    }
}

查找某个值所在的位置

设需要查找的值为 \(v\)（保证 \(v\) 存在）。
那么就和插入操作很类似了，只是我们当 \(v=val_{pos}\) 的时候，直接返回 \(pos\) 即可
代码如下：

int selpos(int v){
    int pos=root;
    while(true){
        if(val[pos]==v) return pos;
        pos=son[pos][v>val[pos]];
    }
}

删除

设需要删除的值为 \(v\)。
删除操作需要先找到 \(v\) 的位置，删除后，合并他的左右两颗子树即可。
代码如下：

void clear(int pos){
    val[pos]=son[pos][0]=son[pos][1]=fa[pos]=0;
}//清空节点pos
void del(int v){
    int pos=selpos(v);
    if(son[pos][0]==0&&son[pos][1]==0){
        clear(pos);
        return;
    }
    if(son[pos][0]==0&&son[pos][1]!=0){
        fa[son[pos][1]]=fa[pos];
        if(fa[pos]!=0) son[fa[pos]][val[pos]>val[fa[pos]]]=son[pos][1];
        clear(pos);
        return;
    }
    if(son[pos][0]!=0&&son[pos][1]==0){
        fa[son[pos][0]]=fa[pos];
        if(fa[pos]!=0) son[fa[pos]][val[pos]>val[fa[pos]]]=son[pos][0];
        clear(pos);
        return;
    }
    fa[son[pos][0]]=son[pos][1];
    fa[son[pos][1]]=fa[pos];
    if(fa[pos]!=0) son[fa[pos]][val[pos]>val[fa[pos]]]=son[pos][1];
    clear(pos);
}

更多操作

• 查询 \(v\) 这个值的排名
  
• 查询 \(x\) 这个排名的值
  
• 查询 \(v\) 这个值的前驱
  
• 查询 \(v\) 这个值的后继

请读者自行尝试或者查阅，因为普通的二叉搜索树容易被卡，因此在后文讲解 Splay 时具体讲解。

复杂度分析

空间复杂度：

我们每次在插入时只会多一个，因此空间复杂度为 \(O(n)\)

时间复杂度：

理想情况下，\(n\) 个数据构成的二叉树的高度为 \(\log{n}\) 因此在插入删除时均最多跳 \(\log{n}\) 次，最优时间复杂度为 \(O(\log{n})\)。
但是我们可以通过构造如 1 2 3 4 5 这样单调的数据，来使树高变为 \(O(n)\)，此时二叉搜索树退化为链，插入和删除时最多会跳 \(n\) 次，最劣时间复杂度为 \(O(n)\)。

总之，普通的二叉搜索树没法保证时间复杂度，我们需要优化。

Splay

Splay 是一种自平衡的 二叉搜索树。
（ps：关于更多平衡树，以后会讲）

Splay 通过一种叫做 Splay 的操作，防止二叉搜索树退化为链，保证了树高为 \(O(\log{n})\) 级别，保证了各个操作的 \(O(\log{n})\) 时间复杂度。

基础操作

直接上代码吧：

void clear(int x){
    fa[x]=val[x]=son[x][0]=son[x][1]=cnt[x]=siz[x]=0;
}//清空x节点
void pushup(int x){
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x];
}//更新x节点的子树大小
bool get(int x){
    return x==son[fa[x]][1];
}//得到点x属于fa[x]的左儿子还是右儿子

旋转操作

若你学过 Treap 之类的带旋平衡树，这一部分可以选择略过（建议不要略过）。

由中序遍历的性质：同一种中序遍历对应的二叉树不止一棵。
我们可以通过一些操作，在保证中序遍历不变的前提下，来使树高变低。
这种操作就称作 旋转操作，函数一般叫做 rotate。

为什么要旋转

对于这么一棵二叉树。

我们要将其转成这样：

当然也可以转回来，
这样进行一次旋转后，x的高度提高了一层。
看似对总的高度没有影响，
但对于这样的退化成链的情况时：

我们可以通过如下操作，将高度降低。

1. 对点 \(1\) 进行旋转操作，会变成这样：

2. 再对点 \(1\) 进行旋转操作，会变成这样：

3. 继续对点 \(1\) 进行旋转操作，会变成这样：

4. 最后对点 \(3\) 进行旋转操作，会变成这样：

至此，我们成功地通过旋转操作将高度从 \(4\) 降到 \(3\)。
因此旋转操作是可以有效降低树高的。

旋转过程讲解

我们令要进行 rotate 操作的点为 \(x\)。
令:
\(y \gets fa[x]\)
\(z \gets fa[y]\)
\(ch \gets get(x)\)

根据这两个图：

我们可以发现：
（ps：\(a \oplus b\) 表示 "\(a\) 异或 \(b\)"）
（此时的 \(ch=0\)）

• \(son_{x,ch}\) 没有发生变化
  
• \(son_{x,ch \oplus 1}\) 变成了 \(y\)
  
• \(son_{y,ch}\) 从 \(x\) 变成了 \(son_{x,ch \oplus 1}\)
  
• 对应的 \(fa\) 的的值也会随之变化

最后再处理一下先后执行顺序，就可以写出旋转操作的代码啦~~

代码

void rotate(int x){
    int y=fa[x],z=fa[y];bool ch=get(x);
    son[y][ch]=son[x][ch^1];
    if(son[x][ch^1]!=0) fa[son[x][ch^1]]=y;
    son[x][ch^1]=y;
    fa[y]=x;
    fa[x]=z;
    if(z!=0) son[z][y==son[z][1]]=x;
    pushup(y);
    pushup(x);
}

Splay操作

Splay 规定，每次操作后，都要将操作的点转到根上，这样的操作就被称为 Splay操作。
怎么转移到根上？暴力一次次往上旋转即可。

单旋Splay

如果只是像上文那样旋转，也就是从下往上依次转，这样的被称为 单旋Splay。
当出现 \(x,y,z\) 三点共线时，我们发现，依此转完后，树高是没有变化的，这样就没法保证时间复杂度（见下面几张图理解）。

我们需要将 \(1\) 号点转到根上。

那么我们只需要旋转四次 \(1\) 号点就可以了。
转的过程如下：

这样的话，就是“如转”。
我们虽然将 \(1\) 号点转到了根上，但是高度并没有降低。
因此当树退化为一条链的时候。
单旋Splay 也就没法保证时间复杂度了。

这时候我们就需要用到 双旋Splay。

双旋Splay

双旋Splay 其实就是在 单旋Splay 的基础上，特殊处理了一下 \(u,v,z\) 三点共线的情况
在遇到三点共线的情况时，我们只需要先旋转 \(fa_{u}\) 也就是 \(v\) 点，再旋转 \(u\) 点即可。
因为我们在旋转某个点的时候，这个点的整个子树都会一起上升 \(1\) 层。
因此我们先转 \(v\)，后转 \(u\) 是合法的。
（见下图模拟，我们依然需要将 \(1\) 号点转到根上）

\(1,2,3\) 号点共线，因此先转 \(2\) 号点，再转 \(1\) 号点。

\(1,4,5\) 号点共线，因此先转 \(4\) 号点，再转 \(1\) 号点。

可见，双旋Splay 不仅将我们需要的点转到了根上。
而且将原来的不优美的链，变得优美了一些些。
高度也就降低了。
因此 双旋Splay 更优。

代码如下：

void Splay(int x){
    for(int f=fa[x];f;f=fa[x]){
        if(fa[f]!=0) rotate(get(x)==get(f)?f:x);
        rotate(x);
    }
}
//忘记了 get 函数是做什么的，去前面看看吧xwx

现在我们学会了 Splay操作，那么其实也就很简单了，只需要像普通的二叉搜索树一样进行操作基本就行了，记住每次操作完后，将最后找到的点通过 Splay操作 转到根上去就可以了。

插入

因为 Splay 本质上也是二叉搜索树，因此它满足二叉搜索树有的所有性质。
插入方式和普通二叉搜索树一样，记住最后将插入的那个点旋转到根上即可~

代码如下：

void insert(int x){
    if(root==0){
        val[++tot]=x;
        cnt[tot]++;
        pushup(tot);
        root=tot;
        return;
    }
    int f=0,pos=root;
    while(true){
        if(val[pos]==x){
            cnt[pos]++;
            pushup(pos);
            pushup(f);
            Splay(pos);//记住Splay操作！！！
            return;
        }
        f=pos;
        pos=son[pos][x>val[pos]];
        if(pos==0){
            val[++tot]=x;
            cnt[tot]++;
            fa[tot]=f;
            son[f][x>val[f]]=tot;
            pushup(tot);
            pushup(f);
            Splay(tot);//记住Splay操作！！！
            return;
        }
    }
}

查询排名

设当前访问到的点是 \(pos\)，答案为 \(ans\)，最开始 \(ans \gets 1\)（因为排名至少为 \(1\)）。
查询 \(x\) 这个值的排名可以分为三种情况：

1. \(x > val_{pos}\)：
   说明 \(pos\) 这个点的左子树的所有值和 \(pos\) 这个点的值都小于 \(x\)
   那么排名至少为 \(cnt_{son_{pos,0}}+cnt_{pos}\)
   即 \(ans \gets ans+cnt_{son_{pos,0}}+cnt_{pos}\)
   然后继续到右子树中计算答案，即 \(pos \gets son_{pos,1}\)
   
2. \(x = val_{pos}\)：
   说明 \(pos\) 的左子树的所有值都小于 \(x\)
   并且 \(pos\) 这个点的值刚好等于 \(x\)
   因此排名就应该是 \(ans \gets ans+siz_{son_{pos,0}}\)
   
3. \(x < val_{pos}\)：
   说明 \(pos\) 的左子树有比 \(x\) 大的值。
   因此此时不能对答案进行计算。
   需要继续到左子树中计算答案，即 \(pos \gets son_{pos,1}\)

代码如下：

int selrank(int x){
    int res=0,pos=root;
    while(true){
        if(x==val[pos]){
            Splay(pos);//将pos转到根后，其左子树就是答案，其实和前文表述是一样的
            return siz[pos[son][0]]+1;
        }
        if(now==0) break;
        if(x<val[pos]) pos=son[pos][0];
        else{
            res+=siz[son[pos][0]]+cnt[pos];
            pos=son[pos][1];
        }
    }
    return res+1;   
}

查询排名对应的值

查询排名对应的值其实和查询值对应的排名很像。
设当前访问到的点是 \(pos\)，要找排名为 \(x\) 的值。
一样分为3种情况：

1. \(x > siz_{son_{pos,0}}+cnt_{pos}\)：
   说明答案在 \(pos\) 的右子树中。
   因此将 \(x \gets x-(siz_{son_{pos,0}}+cnt_{pos})\)
   再到右子树（\(pos \gets son_{pos,1}\)）中寻找答案即可。
   
2. \(siz_{son_{pos,0}} < x \le siz_{son_{pos,0}}+cnt_{pos}\)：
   说明答案就是 \(val_{pos}\)
   直接返回答案即可。
   
3. \(x \le siz_{son_{pos,0}}\)：
   说明答案在 \(pos\) 的左子树。
   到左子树（\(pos \gets son_{pos,0}\)）中继续寻找答案即可。

代码如下：

int selval(int x){
    int pos=root;
    while(true){
        if(x<=siz[son[pos][0]]){
            pos=son[pos][0];
            continue;
        }
        x-=siz[son[pos][0]]+cnt[pos];
        if(x<=0){
            Splay(pos);//记住Splay操作！！！
            return val[pos];
        }
        pos=son[pos][1];
    }
}

查询前驱

前驱被定义为比 \(x\) 小的数中最大的数。
因此我们只需要从根的左子树开始，一直跳右儿子即可。

代码如下：

int selpre(){
    int pos=son[root][0];
    while(son[pos][1]!=0) pos=son[pos][1];
    Splay(pos);//记住Splay操作！！！
    return pos;
}

注意：这个是找的是当前根所对应的值的前驱，如果需要查找任意一个数的前驱，可以先插入这个数，查完后再删除即可。

也就是：

int selpre_val(int x){
    int res;
    insert(x);
    res=val[selpre()];
    del(x);
    return res;
}

查询后继

查找后继和前驱基本一致，只是开始从根的左儿子变成了右儿子，跳左儿子变成了跳右儿子。

int selnext(){
    int pos=son[root][1];
    while(son[pos][0]!=0) pos=son[pos][0];
    Splay(pos);//记住Splay操作！！！
    return pos;
}

查找任意一个数的后继和查找任意一个数的前驱是同样的道理：

int selpre_val(int x){
    int res;
    insert(x);
    res=val[selnext()];
    del(x);
    return res;
}

合并两颗Splay树

两颗 Splay树 想要快速合并，前提条件是一棵树的最大值小于另一棵树的最小值，否则无法做到快速合并。

合并分为三种情况:

1. 两棵子树均为空，不用管。
   
2. 一棵子树为空，直接把不为空的子树的根作为合并后的根即可。
   
3. 两边子树均不为空，将第一棵子树的最大值转到根上，将左儿子设为另一颗树的根，\(fa\) 数组也跟着更新即可，最后合并出的根就是第一棵子树的根。

为什么要将一棵树的最大值转到根后再合并？因为这样才能保证第一棵子树的右儿子是空的，才能够合并上去。

代码如下：

int merge(int x,int y){//这里传的是两个树的根，返回值是合并后的根
    if(x==0||y==0) return x+y;
    int pos=x;
    while(son[pos][1]!=0) pos=son[pos][1];
    Splay(pos);//记住Splay操作！！！
    son[pos][1]=y;
    fa[y]=pos;
    pushup(pos);
    return pos;
}

删除

删除操作相对比较复杂。
因此放在最后面来讲 需要先将要删的这个点转到根上。
如果这个点的 \(cnt\) 值大于 \(1\)，那么直接将 \(cnt_{pos} \gets cnt_{pos}-1\) 即可。 然后再找到这个点的前驱。
将前驱作为新的根，合并两颗子树。

为什么要找前驱？
因为在当前你要删除的这个点的右子树中，只有前驱可以保证没有右儿子。
合并两棵子树也就是 \(O(1)\) 的了。

代码如下：

void del(int x){
    selrank(x);//这里的作用是将x转到根上
    if(cnt[root]>1){
        cnt[root]--;
        pushup(root);
        return;
    }
    if(son[root][0]==0&&son[root][1]==0){
        clear(root);
        root=0;
        return;
    }
    if(son[root][0]==0&&son[root][1]!=0){
        int past=root;
        root=son[root][1];
        fa[root]=0;
        clear(past);
        return;
    }
    if(son[root][0]!=0&&son[root][1]==0){
        int past=root;
        root=son[root][0];
        fa[root]=0;
        clear(past);
        return;
    }
    int past=root;
    int pos=selpre();//此时的pos已经成为根了，所以不用Splay操作了
    fa[son[past][1]]=pos;
    son[pos][1]=son[past][1];
    clear(past);
    pushup(root);
}

代码

至此，你已经会了 Splay 的绝大多数操作了
板子的代码也放在这里了~

ps：亲测本人 Splay 代码可以通过加强版模板题

代码如下：

// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,x,tot,root,val[MAXN],siz[MAXN],cnt[MAXN],fa[MAXN],son[MAXN][2];
inline int read(){
    register int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
void clear(int x){
    fa[x]=val[x]=son[x][0]=son[x][1]=cnt[x]=siz[x]=0;
}
void pushup(int x){
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x];
}
bool get(int x){
    return x==son[fa[x]][1];
}
void rotate(int x){
    int y=fa[x],z=fa[y],ch=get(x);
    son[y][ch]=son[x][ch^1];
    if(son[x][ch^1]!=0) fa[son[x][ch^1]]=y;
    son[x][ch^1]=y;
    fa[y]=x;
    fa[x]=z;
    if(z!=0) son[z][y==son[z][1]]=x;
    pushup(y);
    pushup(x);
}
void splay(int x){
    for(int f=fa[x];f;f=fa[x]){
        if(fa[f]) rotate(get(x)==get(f)?f:x);
        rotate(x);
    }
    root=x;
}
void insert(int x){
    if(root==0){
        val[++tot]=x;
        cnt[tot]++;
        pushup(tot);
        root=tot;
        return;
    }
    int now=root,f=0;
    while(true){
        if(val[now]==x){
            cnt[now]++;
            pushup(now);
            pushup(fa[now]);
            splay(now);
            break;
        }
        f=now;now=son[now][x>val[now]];
        if(now==0){
            val[++tot]=x;
            cnt[tot]++;
            fa[tot]=f;
            son[f][x>val[f]]=tot;
            pushup(tot);
            pushup(f);
            splay(tot);
            break;
        }
    }
}
int selrank(int x){
    int res=0,now=root;
    while(true){
        if(x==val[now]){
            splay(now);
            return siz[son[now][0]]+1;
        }
        if(now==0) break;
        if(x<val[now]) now=son[now][0];
        else{
            res+=siz[son[now][0]]+cnt[now];
            now=son[now][1];
        }
    }
    return res+1;
}
int selval(int x){
    int now=root;
    while(true){
        if(x<=siz[son[now][0]]&&son[now][0]!=0) now=son[now][0];
        else{
            x-=siz[son[now][0]]+cnt[now];
            if(x<=0){
                splay(now);
                return val[now];
            }
            now=son[now][1];
        }
    }
}
int selpre(){
    int now=son[root][0];
    while(son[now][1]!=0) now=son[now][1];
    splay(now);
    return root;
}
int selnext(){
    int now=son[root][1];
    while(son[now][0]!=0) now=son[now][0];
    splay(now);
    return root;
}
void del(int x){
    selrank(x);
    if(cnt[root]>1){
        cnt[root]--;
        pushup(root);
        return;
    }
    if(son[root][0]==0&&son[root][1]==0){
        clear(root);
        root=0;
        return;
    }
    if(son[root][0]!=0&&son[root][1]==0){
        int past=root;
        root=son[root][0];
        fa[root]=0;
        clear(past);
        return;
    }
    if(son[root][0]==0&&son[root][1]!=0){
        int past=root;
        root=son[root][1];
        fa[root]=0;
        clear(past);
        return;
    }
    int past=root;
    int pos=selpre();
    fa[son[past][1]]=pos;
    son[pos][1]=son[past][1];
    clear(past);
    pushup(root);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int opt,x;
        opt=read();x=read();
        if(opt==1) insert(x);
        if(opt==2) del(x);
        if(opt==3) cout<<selrank(x)<<endl;
        if(opt==4) cout<<selval(x)<<endl;
        if(opt==5){insert(x);cout<<val[selpre()]<<endl;del(x);}
        if(opt==6){insert(x);cout<<val[selnext()]<<endl;del(x);}
    }
    return 0;
}

接下来，就正式进入 LCT 的部分了~

LCT

现在，你应该已经掌握了所有的前置芝士，是时候真正进入LCT的部分了！！！

讲解

首先，我们称原来的树叫做原树。
现在，我们为了实现删边和连边的操作，引入一棵新的树，叫做辅助树。
注意！！！千万千万不要把这两棵弄混了！！！
在下文中，我会将有关这两棵树的地方用不同的颜色标出。
这是\(\textcolor{green}{原树}\)，这是\(\textcolor{blue}{辅助树}\)。

既然 LCT 又叫做虚实链剖分，那么肯定和一般的树剖有相似之处。
我们定义有两种树边，一种是实边，一种是虚边，对应的连接的儿子也就分别是实儿子和虚儿子。
\(\textcolor{green}{原树}\)中有儿子的节点一定有且仅有一条实边（没有儿子当然也就没有实边），可以有任意多（包括 \(0\)）条虚边。
虚实链都是可以自由变换的，这个特点使得 LCT 可以实现 动态树 这一类问题。
将由实边构成的树上的一条链称为实链。显然，每个点都会且仅会在一条实链上。

\(\textcolor{green}{原树}\)上的每一条实链，在\(\textcolor{blue}{辅助树}\)上对应的则是一棵 Splay。

\(\textcolor{blue}{辅助树}\)有如下性质：

1. \(\textcolor{blue}{辅助树}\)上每个点与\(\textcolor{green}{原树}\)上的每个点一一对应。
   
2. 对\(\textcolor{blue}{辅助树}\)上每一棵 Splay 树进行中序遍历，得到的则是\(\textcolor{green}{原树}\)上这条对应的实链从上到下的路径。
   
3. \(\textcolor{blue}{辅助树}\)上每一棵 Splay 树的根节点是有父亲的。定义为\(\textcolor{blue}{辅助树}\)上这棵 Splay 对应的\(\textcolor{green}{原树}\)上的那条实链的最顶端的节点的父亲。（特别的，最顶端的 Splay 的根节点是没有父亲节点的，或者说它的父亲节点是 \(0\)）
   
4. 在 \(3\) 中提到的父亲关系的特点是儿子认父亲，父亲不认儿子。而\(\textcolor{blue}{辅助树}\)上的每一棵 Splay 内部的父亲关系则是儿子认父亲，父亲认儿子的。
   
5. 在 LCT 上的所有操作，都只需要在\(\textcolor{blue}{辅助树}\)上操作即可，因为每一棵\(\textcolor{blue}{辅助树}\)都会对应唯一的一棵\(\textcolor{green}{原树}\)。

假如我们有这样一棵\(\textcolor{green}{原树}\)：

他的虚实链剖分可能长这样（因为虚实链很自由的原因，所以这并不是唯一一种剖分方式）：

虚线边表示虚边，实线边表示实边。

那么根据定义，这棵\(\textcolor{green}{原树}\)对应的\(\textcolor{blue}{辅助树}\)可能就会是这样的：

那么我们现在就需要思考，\(\textcolor{blue}{辅助树}\)是如何实现 动态树 这么一个难题的呢？

我认为，如果只是去讲具体什么 Access 函数的实现之类的，可能并不能算是真正了解 LCT 的原理，我在这里尽量会讲得更清楚。

如何连边

拿这么两棵树举例：

我们需要把 \(G\) 和 \(B\) 连接起来，那么树就变成这个样子：

我们发现蓝色边无论是实边，还是虚边，都是无法建出一棵合法的\(\textcolor{blue}{辅助树}\)的。因此我们要么在\(\textcolor{green}{原树}\)上作出修改，要么在\(\textcolor{blue}{辅助树}\)上做修改。
根据前文所讲，我们只需在\(\textcolor{blue}{辅助树}\)上做修改即可。
那么我们怎么修改呢？

原先两棵树的\(\textcolor{blue}{辅助树}\)可以是这样的：

那么假如直接连接 \(G\) 和 \(B\) 就会是这样的：

很显然的发现，这样是不合法的，因为 \(G\) 有了两个父亲。
根据\(\textcolor{blue}{辅助树}\)的性质 \(3\)，我们知道，只有整棵\(\textcolor{blue}{辅助树}\)的根节点才是没有父亲的。
因此我们需要把 \(G\) 点变成它所在的\(\textcolor{blue}{辅助树}\)的根的位置。
我们定义一种新的函数叫做 access(x)，表示将 x 这个点与其当前变所在的\(\textcolor{blue}{辅助树}\)的根结点弄到同一个 Splay 中。
那么在这个例子中，我们进行一次 access(G)，再 Splay(G) 一下，最后，连接 \(G\) 和 \(B\)，似乎就达成了任务，此时变为：

但从\(\textcolor{green}{原树}\)的连接情况中我们可以看出：

根据\(\textcolor{blue}{辅助树}\)的性质 \(2\)，在这棵\(\textcolor{blue}{辅助树}\)上，\(I,G,H\) 应该深度依次递增。但我们发现在连接后的\(\textcolor{green}{原树}\)上（假设以 \(A\) 点为根）并不满足这一点，因此目前的连接情况是不合法的。
怎么处理这种情况？
那么很显然的，我们让 \(G\) 这个点变成它所在的\(\textcolor{green}{原树}\)的根就可以了。
我们称这样将某个点变成其所在的\(\textcolor{green}{原树}\)的根的操作为 makeroot(x)，当然，我们只能在\(\textcolor{blue}{辅助树}\)上进行一些操作。
那么这个 makeroot(x) 函数以及前文中的 access(x) 函数分别该怎样实现呢？

access

这里再用上文中的\(\textcolor{green}{原树}\)的例子就不大好了。我们换一棵\(\textcolor{green}{原树}\)：

（这里就直接搬了 OI-Wiki 上的原图了xwx）

（这里以 \(A\) 点为\(\textcolor{green}{原树}\)的根。）
这棵\(\textcolor{green}{原树}\)的\(\textcolor{blue}{辅助树}\)可能长这样：

假如我们想要 access(N)。

也就是将\(\textcolor{green}{原树}\)变为这样：

（红色的边表示的是有虚实边类型切换的边）

为了保证\(\textcolor{blue}{辅助树}\)的性质，我们需要将原来 \(N\) 到 \(O\) 的实边变为虚边。

那么在\(\textcolor{blue}{辅助树}\)上，我们首先需要