一、什么是 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 模板

例 2. P2147 [SDOI2008] 洞穴勘测

【题意简化】给定 $n(\le 10^4)$ 个独立的点，$m(\le 2\times 10^5)$ 次操作．每次操作为以下之一：

• Connect u v：在 $u,v$ 两点之间连接一条边．
• Destroy u v：删除在 $u,v$ 两点之间的边，保证之前存在这样的一条边．
• Query u v：询问 $u,v$ 两点是否连通．

保证在任何时刻图的形态都是一个森林．

【分析】借助 LCT 的 findRoot() 函数(寻找原树的根)，可以判断动态森林上的两点是否连通．

例 3. P2542 [AHOI2005] 航线规划

【题意简化】给定 $n(\le 3\times 10^4)$ 个点 $m(\le 10^5)$ 条边的图，$q(\le 4 \times 10^4)$ 次操作: op=0 删除图中一条边; op=1 询问路径上桥的数量.

【分析】如果不考虑删除操作,询问桥的数量,那么本身就是将图中所有“边双”缩成一个点，图变为树，询问树上两个点之间的路径数量。但是删边操作，没法维护“点双”.

注意题目中只有删除边操作,这种情况如果我们将处理前后颠倒,删边操作就变为加边操作. 如果添加的边已经连通,那么就可以将原路径上的点缩点，否则利用 LCT 加边.

对于路径上所有点缩点的操作，可以利用并查集，访问路径上所有点，并查集合并.

对于查询，LCT 单独取出路径, 答案就是 路径上点的数量 -1 .

例 4. P3950 部落冲突

【题意简化】给定一棵 $n$ 个节点的树, 动态切断或恢复某些边，同时询问树上两个点是否连通.

【分析】本题可以使用 LCT 进行维护两个点是否连通, 这里介绍代码量小的提高组解题思路.

将一条边对应到点上，对应到深度大的点上，方便后续统计删除的数量.

对于删除一条边 x->y ，y 子树内所有点如果往根节点走,会经过这条断边. 如果记 dis[y] 表示 y 到根经过断边的数量，那么路径 x---y 断边数量就是 dis[x]+dis[y]-2*dis[lca] , 如果这个数量不为 0 , 就说明路径不通.

问题就转换为删除/恢复一条边,快速更新树中 dis .当删除一条边 x->y，需要给将 y 子树内所有节点 dis 加 1 , 恢复时 减 1. 利用 dfs 序，子树对应 dfs 一段区间,问题就可以变成区间修改了。

---

例 5. P4234 最小差值生成树

【题意简化】给定一个点标号从 $1$ 到 $n(\le 5 \times 10^4)$ 的、有 $m(\le 2\times 10^5)$ 条边的无向图，求边权最大值与最小值的差值最小的生成树。图可能存在自环。保证图连通。

【分析】如果对 $m$ 条边排序, 类似于双指针, 动态维护一个生成树 . 但是我们发现当一条边两个端点已经连通时，需要删除路径上的最小边权，为了好寻找路径上最小边权对应的边，我们将边转化为点，Splay 维护实链上最小值对应的编号 . 利用 LCT 动态连接一条边, 或者断开路径上的最小边.

为了方便维护最小生成树最小边权，利用 multiset<> 方便删除插入。

【参考代码】点击

例 6. P2387 [NOI2014] 魔法森林

---

例 7. P4219 [BJOI2014] 大融合

【题意简化】给定 n 个结点和 q 次操作，每个操作为如下形式：

• A x y 在结点 x 和 y 之间连接一条边．
• Q x y 给定一条已经存在的边 (x,y)，求有多少条简单路径，其中包含边 (x,y)．

保证在任意时刻，图的形态都是一棵森林．

$1 ≤𝑛,𝑞,𝑥,𝑦 ≤10^5$

【分析】由于题目中任何时候都是森林，断开 x-y 后，与 x 连通点的数量 siz[x] ,与 y 连通的点的数量 siz[y] ,那么询问简单路径的数量就是siz[x]*siz[y].

LCT 不擅长维护原树对应子树节点数量，为了维护子树数量，增加一个数组 siz2[x] , 统计 x 所有虚儿子.

siz[x] 为 x 子树中所有儿子数量.

在 Splay 内部操作的都是实边，虚边没有发生改变，那么就不需要修改 siz2[] ,只需要修改 siz[] , 也就是 pushup 函数，如下:

void pushup(int x){
        siz[x]=siz[ch[x][0]]+1+siz[ch[x][1]]+siz2[x];
    }

在 Splay 内部的操作，没有涉及到虚实边改变，siz2[] 不需要修改，也就是 rotate()/splay() 函数都不用任何变动。

而对于 access() 需要修改虚实边，修改如下:

void access(int x){
        for(int p=0; x;p=x,x=fa[x]){
            splay(x);
            //重要 
            // x-p 原来是虚边，现在要变为实边 -siz[p]
            //x - ch[x][1] 原来是实边，现在要变为虚边 +siz[ch[x][1]]
            siz2[x] +=siz[ch[x][1]]-siz[p];
            ch[x][1]=p;
            pushup(x);
        }
    }

对于连边操作，本质是连接了一条虚边，那么必然修改 siz2[] , 连边函数修改如下:

    void link(int x,int y)  //题目中保证 x y 没有连边
    {
        makeroot(x); makeroot(y);
        fa[x]=y; siz2[y]+=siz[x];  //建立虚边 更新 siz2
        pushup(y);
    }

对于删边操作，经过 access() ,删除的是实边，虚边没有发生变化，siz2[] 没有改变， siz[x] 通过 pushup() 函数更新了，因此没有变动。

【参考代码】点击

---

学习完毕

{{ select(1) }}

• YES
• NO