浅谈LCT

lgsrw31415 · 2025-10-03 16:44:36 · 算法·理论

动态树 LCT (Link - Cut - Tree)

一、什么是 LCT ？

先给出一道题：

给出一棵树，每个点都有点权，要求进行一些操作：

1. 将树上两个点间的简单路径上的点的点权加上某个数
2. 统计树上两个点间的简单路径上的点的点权之和

很显然，这是一道树链剖分的模板题，只需要求出每个点的重儿子就行了（重儿子是指其子树节点数最多的一个儿子）。

然而，倘若我们增加两种操作：连边与断边。使这个问题由一棵树上的操作变成一片森林的操作，树链剖分就不管用了，那么这时，我们该怎么办呢？

相信你已经想到了，那就是我们今天的主角—— LCT ！

动态树，顾名思义，就是一种用对数复杂度处理一些形态会改变的树上问题。非常的好用。

二、LCT 的原理

1. 建立辅助树

LCT 的原理很简单，简单概括就是 splay 树 + 树链剖分。 倘若再进行连边与断边操作时，我们直接在原树上修改，就会影响我们先前做的处理，导致我们很难统计链上的信息。

因此我们建立一棵辅助树，使得原树与辅助树能够相互转换，就能够通过改变辅助树来改变原树的形态。

那么这棵辅助树该怎么建呢？

实际上我们还是使用树链剖分，不过由于树的结构是变化的，所以提前剖好所有的链没有意义，因此这里的树链剖分既不是重链剖分，也不是长链剖分。

我们给出一棵树。

对它进行剖分，我们把剖出的边（加粗的）称为实边，其余的称为轻边，其中多条实边可以构成实链（注意：实边不一定要覆盖整棵树，也可以整棵树没有一条实边，全都是轻边）

在剖好链之后，我们将每条实链的节点按从上到下的顺序建一棵 splay 树，其中 splay 树的中序遍历就是原树实链上从上到下的顺序，比如原树上的 1 - 2 - 4 这条实链，建好后就长这样。

再比如 6 - 9 这条链，建好后就长这样。

但是，现在还有一个问题，原树上的轻边怎么办呢？很简单，直接挂上去就行了，就比如说 1 - 2 - 4 这条实链中 1 还有一条轻边连接 3，直接在辅助树上连接。

不过，实际上辅助树不应该这么连，因为 3 在他所在的 splay 树上有它自己的父亲(除非它在 splay 树上是根节点)因此，应该将 1 与 3 所在 splay 树上的根节点连边。

通过这些方法，我们就能建出辅助树，容易发现，由辅助树的形态可以还原出原树的形态，因此我们接下来直接在辅助树上操作就可以了。

2. \text{access}(x) 操作

首先，我们将 9 旋转到它所在 splay 树的根，并断开与右儿子的联系。不过这里没有右儿子。

其次，我们将 9 现在的父节点 3 （也是它在原树上的父节点）旋转到它所在 splay 树的根并将右儿子替换为 9。

（为什么是右儿子？ 因为 9 在原树上比 3 深度多 1，因此在 splay 树上的中序遍历顺序也应该比 3 多 1，也就是成为 3 的右儿子）

然后我们再不断进行以上操作直到找到根节点，这样，我们就建出一条起点为原树根节点，终点为 9 的一条实链了。

3. \text{reverse}(x) 操作

2.虚实链转换

参考树链剖分，定义两种虚边：

• 重虚边：v 连向父亲的虚边，其中 size(v)\ge \frac{1}{2} size(parent(v))
• 轻虚边：v 连向父亲的虚边，其中 size(v)\le \frac{1}{2} size(parent(v))

对于虚边的处理，可以使用势能分析，定义势能函数 \Phi 为所有重虚边的数量，定义均摊成本 c_i = t_i + \Delta \Phi_i，其中 𝑡_𝑖 为实际操作的成本，\Delta \Phi_i 为势能的变化。

• 走过重虚边后，会将重虚边转换为实边，该操作会减少 1 的势能，因为它通过加强重要连接来优化树的结构。且由于其实际操作成本为 𝑂(1)，抵消了势能的增加，故不会增加均摊成本，所有的均摊成本集中在轻虚边的处理上。

• 每次 \text{access} 操作最多遍历 O(\log n) 条轻虚边，因此至多消耗 O(\log n) 的实际操作成本，转化得到 O(\log n) 条重虚边，即势能以 O(\log n) 的代价增加。

由此，最终访问虚边的均摊复杂度为实际操作成本和势能变化的和，即 O(\log n)。

综上所述，LCT 中 \text{access} 操作的时间复杂度是 \text{splay} 操作和虚边访问的复杂度之和，因此最后的均摊复杂度为 O(\log n)。

四.程序实现

1.结构体定义

#include<bits/stdc++.h>
#define ls ch[0]
#define rs ch[1]
using namespace std;
struct stu{
    int fa,ch[2];
  //虚边中子节点指向父亲，但父节点不指向儿子
  //只有实边的父亲儿子才会互相记录
    int val,sum;
    int tag;//reserve操作的翻转标记
}t[N];

2.\text{isroot} 操作（查找某节点是否为该节点所在 splay 树的根）

bool isroot(int u){return t[t[u].fa].ls!=u&&t[t[u].fa].rs!=u;}
//当此节点为splay树的根时，它的父亲不会记录它

3.\text{pushup} 操作（信息上传）

void pushup(int u){
    t[u].sum=t[t[u].ls].sum+t[t[u].rs].sum+t[u].val;
}

4.\text{reserve} 操作（翻转左右子树）

void reverse(int u){
    if(!u)return;
    swap(t[u].ls,t[u].rs);//翻转左右子树
    t[u].tag^=1;//打标记
}

5.\text{pushdown} 操作（标记下传）

void pushdown(int u){
    if(t[u].tag){
        reverse(t[u].ls);
        reverse(t[u].rs);
        t[u].tag=0;
    }
}

6.\text{push} 操作（标记全部下传）

void push(int u){
    if(!isroot(u))push(t[u].fa);
  //一定要先遍历父亲再下传，否则父亲标记残留可能导致信息下传错误
    pushdown(u);
}//为后续splay准备

7.\text{rotate} 操作

void rotate(int u){
    int f=t[u].fa;
    int g=t[f].fa;
    int k=(u==t[f].rs);
    if(!isroot(f)){
        if(t[g].ls==f)t[g].ls=u;
        else t[g].rs=u;
    }
    t[u].fa=g;
    t[f].ch[k]=t[u].ch[k^1];
    if(t[u].ch[k^1])t[t[u].ch[k^1]].fa=f;
    t[u].ch[k^1]=f;
    t[f].fa=u;
    pushup(u),pushup(f);//更新链上信息
}

8.\text{splay} 操作

void splay(int u){
    push(u);
    while(!isroot(u)){
        int f=t[u].fa,g=t[f].fa;
        if(!isroot(f)){
            if((t[f].ls==u)==(t[g].ls==f))rotate(f);
            else rotate(u);
        }
        rotate(u);
    }
    pushup(u);//更新链上信息
}

9.\text{access} 操作

void access(int u) {
    for(int child=0;u;child=u,u=t[u].fa)//让原先的u成为儿子，建立实边
    {
        splay(u);//将当前节点u旋转到其所在辅助助树的根位置
        t[u].ch[1] = child;//将u的右孩子设为child
        pushup(u);//更新链上信息
    }
}

10.\text{makeroot} 操作

void makeroot(int u){
    access(u),splay(u),reverse(u);
}

11.\text{split} 操作

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

12.\text{link} 操作

void link(int x,int y){
    makeroot(x),t[x].fa=y;
}//连边时一定要判断两点是否连通！否则会产生环。

13.\text{cut} 操作

void cut(int x,int y){
    split(x,y);
    if(t[y].ch[0]!=x||t[x].ch[1])return;//x和y之间没有连边
    t[x].fa=t[y].ch[0]=0;
    pushup(y);
}

14.\text{findroot} 操作（查找节点所在树上的根）

int findroot(int u){
    access(u),splay(u);//access(u)后链的顶端就是根
    while(t[u].ls)u=t[u].ls;
    return u;
}

所有函数

#include<bits/stdc++.h>
#define ls ch[0]
#define rs ch[1]
using namespace std;
const int N=3e5+5;
int n,m,k,x,y;
struct stu{
    int fa,ch[2];
    int val,sum;
    int tag;
}t[N];
bool isroot(int u){return t[t[u].fa].ls!=u&&t[t[u].fa].rs!=u;}
void pushup(int u){
    t[u].sum=t[t[u].ls].sum+t[t[u].rs].sum+t[u].val;
}
void reverse(int u){
    if(!u)return;
    swap(t[u].ls,t[u].rs);
    t[u].tag^=1;
}
void pushdown(int u){
    if(t[u].tag){
        reverse(t[u].ls);
        reverse(t[u].rs);
        t[u].tag=0;
    }
}
void push(int u){
    if(!isroot(u))push(t[u].fa);
    pushdown(u);
}
void rotate(int u){
    int f=t[u].fa;
    int g=t[f].fa;
    int k=(u==t[f].rs);
    if(!isroot(f)){
        if(t[g].ls==f)t[g].ls=u;
        else t[g].rs=u;
    }
    t[u].fa=g;
    t[f].ch[k]=t[u].ch[k^1];
    if(t[u].ch[k^1])t[t[u].ch[k^1]].fa=f;
    t[u].ch[k^1]=f;
    t[f].fa=u;
    pushup(u),pushup(f);
}
void splay(int u){
    push(u);
    while(!isroot(u)){
        int f=t[u].fa,g=t[f].fa;
        if(!isroot(f)){
            if((t[f].ls==u)==(t[g].ls==f))rotate(f);
            else rotate(u);
        }
        rotate(u);
    }
    pushup(u);
}
void access(int u){
    for(int child=0;u;child=u,u=t[u].fa){
        splay(u);
        t[u].ch[1]=child;
        pushup(u);
    }
}
void makeroot(int u){
    access(u),splay(u),reverse(u);
}
void split(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
void cut(int x,int y){
    split(x,y);
    if(t[y].ch[0]!=x||t[x].ch[1])return;
    t[x].fa=t[y].ch[0]=0;
    pushup(y);
}
int findroot(int u){
    access(u),splay(u);
    while(t[u].ls)u=t[u].ls;
    return u;
}

五.其他技巧

1.查询深度

先将节点 \text{access} 一遍，再 \text{splay} 到根，最后所在实链的 \text{size} 就是该节点在原树上的深度。（根在实链顶端，x 在实链底端，此时根与 x 的距离就是实链的节点数减一，因此 x 的深度就是实链的节点数减一再加一，也就是实链的节点数）

2.查询 LCA

若要求节点 x，y 的 LCA ，则先建一条从根到 x 的实链，再建一条从根到 y 的实链，接着将 x 旋转到根，然后会有三种情况：

容易发现，第二、三种情况都是返回 x 此时的父亲，因此将它们合并为一种。

于是原来的三种情况就变为了两种情况：x 为 y 的祖先和 x 不为 y 的祖先。

代码实现：

int lca(int x,int y){
    if(x==y)return x;//特判x和y为同一节点 
    access(x);//建一条从根到x的实链
    access(y);//建一条从根到y的实链
    splay(x);//将x旋转为splay树的根
    if(t[x].fa==0)return x;//x为y的祖先
    return t[x].fa;//x不为y的祖先 
}

六.习题

P3690 【模板】动态树（LCT）

这是动态树的模板题，需要把刚才代码中 pushup 操作的加法改成异或。

注意：在连边时要通过 \text{findroot} 操作判断两点是否连通。

P1501 [国家集训队] Tree II

这题在原来翻转标记的基础上增加了加标记和乘标记，需要明确各种标记的下传顺序。

P2173 [ZJOI2012] 网络

这题需要先将图上问题转化成树上问题，它与模板 LCT 的区别在于需要将边权转化为点权，再维护路径信息。

P4299 首都

这道题需要将 LCT 与树的重心结合，通过 LCT 动态维护树的重心，比较考验综合能力。