一、什么是 LCT ?它解决什么问题？

在传统的树形结构问题中，我们常用树链剖分（重链剖分）来处理树上路径查询或询问的问题。但是，这需要满足一个前提条件：树的形态是固定的。

如果需要动态在树上连边或者断边，并且查询路径信息（如路径异或和、最大值等），重链剖分就无能为力了。这就需要使用 Link Cut Tree (LCT)。

LCT 维护一个森林（多棵树组成的集合），它不仅支持树形态动态修改，还能在均摊 $O(\log{N})$ 的时间复杂度内完成各种路径查询和修改。

二、LCT 的核心思想：虚实链剖分和 Splay 树维护

LCT 的核心框架就是 实虚链剖分+Splay 维护实链。

1. 实虚链剖分：实边与虚边

• 根据需要在原树中，每个节点 最多只能有一条“实边” 连向它某一个儿子，连向其他儿子都是“虚边”。（可以理解为根据需要，指定一条边为实边）
• 由实边连接起来的路径称为实链。

2. 辅助树：实链用 Splay 维护，虚边认父不认子

• 原树中每一条实链，我们都用一颗 Splay 树来维护。
• 关键性质：在一颗 Splay 树中，节点的中序遍历顺序，严格对应原树上这条实链从上到下（深度从小到大）的顺序。即 Splay 是按照原树深度作为排序关键字建立的，那么一条实链，对应多种形态的 Splay ，而反过来，多种形态的 Splay 对应的实链是唯一的。

3. 虚边：认父不认子

• 在 Splay 树内部节点通过左右儿子 ch[x][0/1] 和 fa[] 可进行双向访问。本质上维护的是实边。
• 每棵 Splay 树的根节点，会有一个 fa[] 指针指向这颗 Splay 树在原树中的父亲节点。 但是，这个父亲节点的左右指针并不指向这个 Splay 树的根，本质上这是维护一条虚边，是单向的。通过这条虚边可以在原树上找到整个树根。
• 也就是说虚边认父不认子，自底向上单向连接。
• 虚边的作用是为了跳到上一级的实链上。
• 利用虚边认父不认子的性质，可以判断一个点是否是当前 Splay 的根节点。方法如下：

//判断 x 是否是当前 Splay 的根
bool isRoot(int x) { 
    return ch[fa[x]][0] != x && ch[fa[x]][1] != x; 
}

三、核心操作拆解

LCT 的所有复杂功能，是由几个核心基本操作组合而成的。我们逐一攻克。

1. rotate(x) 和 splay(x)

LCT 中 rotate(x) 和 splay(x) 原理相同，但细节有差异。

LCT rotate(x) 核心片段：

void rotate(int x)
{
    int y=fa[x],z=fa[y];
    int r=dir(x);  // x 是 y 的哪个儿子

    //如果 y 不是splay 的根，需要更新 z 的儿子指针
  //【核心区别在此】
    if(isRoot(y)==false)ch[z][dir(y)]=x;
  
    fa[x]=z;

    ch[y][r]=ch[x][!r];
    if(ch[x][!r])fa[ch[x][!r]]=y;

    ch[x][!r]=y;
    fa[y]=x;

    pushup(y);
    pushup(x);
}

在之前普通 Splay 中 ，通常写法是 if(z)ch[z][ch[z][1]==y] = x; 只需要判断 z 是否存在，如果存在让 z 指向 x;

而在 LCT 中 Splay ,多了一个判断 if(isRoot(y)==false) ,判断 y 是否为当前 Splay 的根。

• 为何需要这个判断？

  在 LCT 中 如果 y 是 Splay 的根，那么 y 的父亲 z 就是另外一棵 Splay (另外一个实链)，也就是虚边，虚边认父不认子，不能修改 ch[z][].

LCT 中 splay(x) 是将 x 旋转到 Splay 树根。核心代码如下：

void splay(int x)//将 x 旋转到 splay 的根
{
    update(x);  //旋转前先向上找到 splay 的根 向下传
    for(int y;y=fa[x],isRoot(x)==false;rotate(x))
        if(isRoot(y)==false)
            rotate(dir(x)==dir(y)?y:x);       
}

LCT 的 Splay：终止条件是 isRoot(x) == false 。而普通 Splay 是将 x 旋转到某个目标点 goal 的下方或整个树根，循环条件是 fa[x]!=goal 或 fa[x] == 0 .

LCT 的 Splay 不能用 fa[x]==0 ，因为在 LCT 中，当 x 为 Splay 的根时 fa[x] 是另外一条实链中的点，边 x -> fa[x] 是虚边，所以不能用 fa[x]==0 判断 x 是 Splay 的根。

2. access(x): 打通通往根节点的“任督二脉”

access(x) 是 LCT 的基石。作用是：在原树中，把从节点 $x$ 到原树根节点所在的路径全部变成实链，并把 $x$ 和它原树中的下级节点断开（变为虚边）。$x$ 就是这条实链中最深的点。

int access(int x) {
    int p;
  //注意 p=0 ，第一次会断开 x 下面的实链
    for (p = 0; x; p = x, x = fa[x]) {
        splay(x);        // 1. 把 x 旋转到当前所在的 Splay 树的根
        ch[x][1] = p;    // 2. 更改 x 的右儿子为 p（因为 p 的深度比 x 大）
        pushup(x);       // 3. 更新节点信息
    }
    return p;
}

运行逻辑： 从 $x$ 向上爬， 利用 Splay(x) 将 $x$ 调整到当前 Splay 树的根，修改 $x$ 的右儿子为虚边对应的 $p$ 那么之前实边就变成了虚边，之前的虚边就变成了实边，一举两得。

3. makeroot(x)： 换根大法

修改或询问一条路径，我们需要先将一条路径中的一个端点变成整个树的根，这就需要换根。

我们需要首先用 access(x) ，在原树上先打通 x 与根；再利用 Splay(x) 在 Splay 树上调整为 Splay 的根，但实际此时原树的根没有改变。但是此时在 Splay 上 $x$ 是深度的节点，Splay 对应原树根到 x 的实链， 如果此时 Splay 整体一翻转，x 就是原树的根了，所以第三步就是翻转当前 Splay,当然只需要打懒惰标记就可以了。

void makeroot(int x) {
    access(x);       // 1. 打通 x 到原树根的路径
    splay(x);        // 2. 把 x 转到 Splay 的根
    pushlazy(x);     // 3. 打上翻转标记
}

运作逻辑： access(x) 之后，x 所在的 Splay 树维护的就是从原根到 x 的路径。执行 splay(x) 后，因为 x 是这条路径上深度最深的点，所以它在 Splay 中一定没有右儿子。 此时我们给 x 打上区间翻转标记（交换左右儿子），x 就变成了 Splay 中深度最浅的点，也就顺理成章地成为了原树的新根！

4. split(x,y) : 提取路径

我们要查询 x 到 y 路径上的异或和，只需要把这条路径单独提取到一棵 Splay 树里。

void split(int x, int y) {
    makeroot(x);     // 1. 让 x 成为原树的根
    access(y);       // 2. 打通从 y 到根（即 x）的路径
    splay(y);        // 3. 把 y 转到 Splay 树的根
}

运作逻辑： 经过这三步，y 及其子树构成的这棵 Splay 树，完美且唯一地包含了从 x 到 y 路径上的所有节点。此时 sum[y] 就是我们要求的路径异或和！

5.动态连边与断边：link & cut

• link(x, y) 连边： 先 makeroot(x) 让 x 做根。为了保证形成的是树而不是环，我们需要检查 x 和 y 是否已经在同一个连通块里。如果不在（findRoot(y) != x），直接让 x 认 y 做父亲（连一条虚边：fa[x] = y）。

// 连接 x 和 y (不在一棵树内)
void link(int x,int y)
{
    makeroot(x);
    if(findRoot(y)!=x){ //判断是否在一颗树内
        fa[x]=y;  //连接虚边，认父不认子
    }
}

• cut(x, y) 断边： 先 makeroot(x)，让 x 成为树根。要断开 x 和 y，必须严格满足三个条件：

1. 它们在一棵树里（findRoot(y) == x）。
2. 在原树中 x 就是 y 的直接父亲（因为 makeroot(x) 后 x 是根，如果它们直接相连，那在提取的 Splay 中 fa[y] 必须是 x）。
3. Splay 中 y 不能有左儿子（保证原树中 x 和 y 之间没有其他深度的节点，即紧挨着）。 满足条件后，断开父子关系并清空儿子指针即可。

void cut(int x,int y)
{
    makeroot(x);
    // 严格判断 x 和 y 之间是否有边
    //1. 它们是否连通 ：findRoot(y)==x
    //2. y 的父亲是 x ：fa[y]==x
    //3. y 没有左儿子，说明 x 紧挨着 y
    if(findRoot(y)==x && fa[y]==x && ch[y][0]==0)
    {
        fa[y]=ch[x][1]=0;
        pushup(x);
    }
}

---

例1. P3690 【模板】动态树（LCT）

【题意简化】给定 $n$ 个点以及每个点的权值，要你处理接下来的 $m$ 个操作，操作有四种，操作从 $0$ 到 $3$ 编号。

• 0 x y 代表询问从 $x$ 到 $y$ 的路径上的点的权值的 $\text{xor}$ 和。保证 $x$ 到 $y$ 是联通的。
• 1 x y 代表连接 $x$ 到 $y$，若 $x$ 到 $y$ 已经联通则无需连接。
• 2 x y 代表删除边 $(x,y)$，不保证边 $(x,y)$ 存在。
• 3 x y 代表将点 $x$ 上的权值变成 $y$。

【分析】LCT 模板题

【参考代码】LCT 模板

---

学习完毕

{{ select(1) }}

• YES
• NO