动态树 link-cut tree

2020luke · 2026-09-21 14:52:58 · 算法·理论

P3690 【模板】动态树（LCT）

动态树，link-cut tree。顾名思义，动态地维护树的结构和各种信息。

https://oi-wiki.org/ds/lct/ :

维护一个森林，支持删除某条边，加入某条边，并保证加边，删边之后仍是森林．我们要维护这个森林的一些信息．

主体思路：将边分类为实边和虚边，类比重链剖分中的重边和虚边，一个点最多只会向一个儿子连出实边。这样我们就将一棵树分成了若干条实边路径，实边路径和实边路径之间由虚边相连，我们只需要维护这些实边路径就等于维护了树。

具体的，我们对于每一条实边路径建一颗 splay 树，这颗 splay 树的节点的中序遍历顺序就是原图上链的深度递增的顺序。注意在这一步区分原图上的节点和 splay 上的节点的关系。

为了用虚边连接起不同的实边路径，我们用 该链对应的 splay 的根 的父亲节点指向 该链顶部的虚边 对应的节点。

注意到，lct 主要解决的是动态树上的链问题，那对于子树问题怎么做呢？这时候，我们 splay 的节点信息就不能仅维护当前点信息，还需要维护 虚儿子 的子树信息，这一部分信息通过虚边转移，每一次树的结构变化，也就是虚边结构变化时我们就更新虚边信息。

考虑原树和辅助树的结构关系 （取自oiwiki）

原树中的实链 : 在辅助树中节点都在一棵 Splay 中．
原树中的虚链 : 在辅助树中，子节点所在 Splay 的 Father 指向父节点，但是父节点的两个儿子都不指向子节点．
注意：原树的根不等于辅助树的根．
原树的 Father 指向不等于辅助树的 Father 指向．
辅助树是可以在满足辅助树、Splay 的性质下任意换根的．
虚实链变换可以轻松在辅助树上完成，这也就是实现了动态维护树链剖分．

接下来我们列出 lct 所需要的函数

splay(x),rotate(x),isroot(x),dir(x) splay 所需的函数

access(x) 建立一条从根到 x 的实边路径，且不向下延申
MakeRoot(x) 使 𝑥 点成为其所在树的根．
Find(x) 找到 𝑥 所在树的根节点编号．
Split(x, y) 提取出 𝑥,𝑦 间的路径，方便做区间操作．
Link(x, y) 在 𝑥,𝑦 两点间连一条边．
Cut(x, y) 把 𝑥,𝑦 两点间边删掉．

变量

可以用结构体封装，效率略有提升因为访存连续性提升，并且面向对象编程易于扩展。这里由于为了方便编写代码使用面向过程的变量编写。

rev 和 stk 都是 lct 的 splay 实现新加入的变量，在 splay 函数中会解释。

int ch[N][2],fa[N],val[N],sum[N];
bool rev[N];
int stk[N];

`access(x)`

建立一条根到 x 的路径，同时将 x 变成 splay 的根节点。需要注意将 x 变为根可以方便其余操作，因为我们没有用变量存下 spaly 的根，所以这样可以清晰的知道根在哪里以方便后续操作

void access(int x) {    //建立一条根到 x 的路径，同时将 x 变成 splay 的根节点
    int z=x;
    for(int y=0; x; y=x,x=fa[x]) {
        splay(x); 
        ch[x][1]=y; pushup(x);
    }
    splay(z);
}

`MakeRoot(x)`

可以先建立一条根到 x 的路径，此时该路径的 splay 中序遍历顺序为根 -> x，我们翻转这颗 splay 就可以变成 x->根的顺序，此时 x 就是这条链上深度最小的节点，也就是根了。

void makeroot(int x) {  //将 x 变为原树的根节点
    access(x);
    pushrev(x);
}

`Find(x)`

access(x)，注意到此时这条链上深度最小的点是根，在对应的 splay 上的中序遍历也就是最左侧节点。

int findroot(int x) {   //找到 x 所在的原树的根节点，再将原树的根节点旋转到 splay 的根节点
    access(x);
    while(ch[x][0]) pushdown(x),x=ch[x][0];
    splay(x);
    return x;
}

`Split(x, y)`

将 x 设为根，并建立 y 到根的路径即可。有了这个功能便能轻松在 lct 上处理链的操作/查询。

注意由于 access(y) 此时 splay 根节点是 y，y 点的信息就代表整条链的信息。

void split(int x,int y) {   //给 x 和 y 之间的路径建立一个 splay，其根节点是 y
    makeroot(x);
    if(findroot(y)==x) {
        access(y);
    }
}

`Link(x, y)`

连接不在同一棵树内的两点。将 x 设为对应树的根，同时也是该棵 splay 的根，并 fa 指向 y 表示向 y 连接一条虚边即可。

void link(int x,int y) {    //如果 x y 不连通，则加入一条 (x,y) 之间的边（虚边）
    makeroot(x);
    if(findroot(y)!=x) {
        fa[x]=y;
    }
}

`Cut(x, y)`

将 x 设为根后如果 x,y 相连，则 access(y) 后，这条链对应的 splay 一定是只有 x,y 两个点，且 x 的右儿子为 y，这里我们只需要保证 y 的左子树为空，也就是 y 除了 x 没有前继节点，此时 x,y 直接相连。

删除操作就把 x,y 对应的儿子/父亲指针设为空即可。

void cut(int x,int y) {     //如果 x y 之间存在边，则删除该边
    makeroot(x);
    if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) {   //findroot(y) 之后 x 为 splay 的根
        ch[x][1]=fa[y]=0;
        pushup(x);
    }
}

`splay(x),rotate(x),isroot(x)`

这一段代码本来应当放在最前面，但是由于相比于常规 spaly 多出了很多特殊操作，所以在列出所有 lct 操作后再解释。

注意到由于有 makeroot 的翻转，所以打上 reverse 的翻转标记并及时 pushdown

注意到，我们有很多的操作是需要直接 splay(x) 也就是从下往上的遍历顺序，例如 accesse 函数中，此时和 pushdown 的传递顺序相反，所以应当先提取 x 到根的路径上的点，再按照深度向下 pushdown 最后再进行操作，这样的顺序才是合理的。

bool dir(int x) {return ch[fa[x]][1]==x;}
// #define dir(x) (ch[fa[x]][1]==x)
void pushup(int x) {
    sum[x]=sum[ch[x][0]]^val[x]^sum[ch[x][1]];
}
void pushrev(int x) {
    swap(ch[x][0],ch[x][1]);
    rev[x]^=1;
}
void pushdown(int x) {
    if(rev[x]) {
        pushrev(ch[x][0]); pushrev(ch[x][1]);
        rev[x]=0;
    }
}
bool isroot(int x) {
    return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
void rotate(int x) {
    int y=fa[x],z=fa[y];
    bool r=dir(x);
    if(!isroot(y)) ch[z][dir(y)]=x; //注意这里必须要先判断isroot,因为修改 fa[y] 会导致isroot判断错误
    fa[x]=z;
    ch[y][r]=ch[x][!r]; if(ch[y][r]) fa[ch[y][r]]=y;
    ch[x][!r]=y; fa[y]=x;
    pushup(y); pushup(x);
}
void splay(int x) {
    int top=0,r=x;
    stk[++top]=r;
    while(!isroot(r)) r=fa[r],stk[++top]=r;
    while(top) pushdown(stk[top--]);
    while(!isroot(x)) {
        int y=fa[x];
        if(!isroot(y)) rotate(dir(y)==dir(x)?y:x);
        rotate(x);
    }
}

完整代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define rep(i,X,Y) for (int i=(X);i<=(Y);++i)
#define per(i,X,Y) for (int i=(X);i>=(Y);--i)
#define FIO(X) freopen(#X".in","r",stdin),freopen(#X".out","w",stdout);
#define mem(X,val) memset(X,val,sizeof(X));
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define se second
#define ALL(X) X.begin(),X.end()
#define pb push_back
#define eb emplace_back
const bool MUL=false;

const int N=3e5+10;

int n,m;

int ch[N][2],fa[N],val[N],sum[N];
bool rev[N];
int stk[N];

bool dir(int x) {return ch[fa[x]][1]==x;}
// #define dir(x) (ch[fa[x]][1]==x)
void pushup(int x) {
    sum[x]=sum[ch[x][0]]^val[x]^sum[ch[x][1]];
}
void pushrev(int x) {
    swap(ch[x][0],ch[x][1]);
    rev[x]^=1;
}
void pushdown(int x) {
    if(rev[x]) {
        pushrev(ch[x][0]); pushrev(ch[x][1]);
        rev[x]=0;
    }
}
bool isroot(int x) {
    return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
void rotate(int x) {
    int y=fa[x],z=fa[y];
    bool r=dir(x);
    if(!isroot(y)) ch[z][dir(y)]=x;
    fa[x]=z;
    ch[y][r]=ch[x][!r]; if(ch[y][r]) fa[ch[y][r]]=y;
    ch[x][!r]=y; fa[y]=x;
    pushup(y); pushup(x);
}
void splay(int x) {
    int top=0,r=x;
    stk[++top]=r;
    while(!isroot(r)) r=fa[r],stk[++top]=r;
    while(top) pushdown(stk[top--]);
    while(!isroot(x)) {
        int y=fa[x];
        if(!isroot(y)) rotate(dir(y)==dir(x)?y:x);
        rotate(x);
    }
}

void access(int x) {    //建立一条根到 x 的路径，同时将 x 变成 splay 的根节点
    int z=x;
    for(int y=0; x; y=x,x=fa[x]) {
        splay(x); 
        ch[x][1]=y; pushup(x);
    }
    splay(z);
}

void makeroot(int x) {  //将 x 变为原树的根节点
    access(x);
    pushrev(x);
}

int findroot(int x) {   //找到 x 所在的原树的根节点，再将原树的根节点旋转到 splay 的根节点
    access(x);
    while(ch[x][0]) pushdown(x),x=ch[x][0];
    splay(x);
    return x;
}

void split(int x,int y) {   //给 x 和 y 之间的路径建立一个 splay，其根节点是 y
    makeroot(x);
    if(findroot(y)==x) {
        access(y);
    }
}

void link(int x,int y) {    //如果 x y 不连通，则加入一条 (x,y) 之间的边（虚边）
    makeroot(x);
    if(findroot(y)!=x) {
        fa[x]=y;
    }
}

void cut(int x,int y) {     //如果 x y 之间存在边，则删除该边
    makeroot(x);
    if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) {   //findroot(y) 之后 x 为 splay 的根
        ch[x][1]=fa[y]=0;
        pushup(x);
    }
}

int Solve() {
    cin>>n>>m;
    rep(i,1,n) cin>>val[i];
    while(m--) {
        int op,x,y; cin>>op>>x>>y;
        if(op==0) {
            split(x,y);
            cout<<sum[y]<<'\n';
        } else if(op==1) {
            link(x,y);
        } else if(op==2) {
            cut(x,y);
        } else if(op==3) {
            splay(x);
            val[x]=y;
            pushup(x);
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int T=1; if(MUL) cin>>T; while (T--) { Solve(); }
    return 0;
}

P2387 [NOI2014] 魔法森林

很不错的入门题。分析题目，将答案贡献拆为 a_i\leq A,b_i\leq B。

可以先将边按照 a_i 从小到大排序并遍历，并逐步将考虑到的边纳入考虑范围，这时我们认定 A=a_i，因为我们只考虑了 a_j\leq a_i=A 的边。为了求得当前状态的最小答案，我们希望能找到一条路径，使得这条路径上的 \max(b) 是最小的，转化成了动态最小瓶颈树的问题

具体的，我们按照 a_i 遍历边时，尝试用 lct 维护由遍历到的边组成的一棵树，使得它满足 \max(b) 最小（最小瓶颈树）。

那么我们在遍历每条边时尝试加入这条边，可以用 lct 动态加边，并统计 (1,n) 路径上的边权最大值。这里引入一个 trick，由于 lct 只能维护点权而不能维护边权，所以对于边 x\stackrel w\to y 我们拆成 x\to a\to y,val_a=w，将边单独拆成一个点，并将该点的点权赋值为边权

但是有可能我们加入这条边后树会产生环，而 lct 是无法维护有环的，所以我们尝试断掉该边对应的两点路径上的一条边，使得能够维持树的状态。

根据直觉想到，如果我们断掉该路径上边权最大的边，并且此时边权最大的边要大于新加入的边权，那么一定是优的。反证法，如果我们断掉的边满足这个条件，我们发现答案一定不会更劣。所以 lct 维护路径上的最大点权，并记录编号，加入新边时判断是否连通，若连通且更优就断掉原路径上的最大权点相连的边，并加入当前边。

P4234 最小差值生成树

发现逻辑其实和上一题大差不差，边权降序枚举，同样的加边时，删除每次路径上的最大边权，统计答案。

P1501 [国家集训队] Tree II

比较典的应用，就是先 split(x,y) 出对应的链，在 splay 上打上两个 tag 即可。

P4172 [WC2006] 水管局长

首次自己想+手码 lct，几乎成功（中间没调过去对比了，好像查出了一个错误，但最主要的不是 lct 的错误）。

考虑到要动态维护树的状态，用 lct 维护。发现这个删边非常难搞，lct 只能维护一棵树的形态。想到能离线然后倒序加边，这样就转换成了动态维护最小瓶颈树。

用类似魔法森林的方法，维护当前的树的形态。若加边时成环，就剪掉环上代价最大的边。这样就可以动态维护图的最小瓶颈树。

查询在 lct 上是简单的，split 出来路径，查询 splay 上的最大值即可。

P4299 首都

重心 trick

https://blog.csdn.net/u013076044/article/details/45915745

树的重心：删去重心后，生成的多棵树尽可能平衡。即以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。

性质

树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。
把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。
一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
树的重心的最大子树 siz≤ 总大小的一半。
如果一个点存在某个儿子的 size 大于等于点数的一半，那么重心在这个儿子的子树中

题解

这道题的核心就在于，我们已经确定了两棵树的重心，用一条边连接两个树，然后在两个重心形成的链上找到新的重心。

回顾重心的性质 2，则新重心一定在原来两个重心形成的链上。性质 4，重心的最大子树 siz\leq 总大小的一半。

我们用 lct 维护树的形态，用 split 函数找出原重心形成的链，根据性质 2&4 在这条链上查找新的重心。

根据性质 4，对于链上的点 x，若 x 左边的 siz 和右边的 siz 均 \leq 总大小的一半，则 x 就是重心。我们 lct 的 splay 维护子树大小时，一个点的 siz 信息维护的是该点的所有虚儿子的子树大小之和，此时 splay 记录的子树信息和就是在 splay 的子树内这些点的 siz 之和。

查找重心时，当我们用 splay 维护树链，我们遍历到了某个点，当前点的子树信息表示的是这条链的某个区间段的信息。因此我们可以在 splay 上用类似线段树二分的方式，不断向下遍历点找到所有的重心。

从 splay 的根开始遍历，左侧的总 size= splay 上 x 的左子树的总 siz + x 子树之外的在 x 遍历顺序前的总 siz。右侧 size 同理。

实现上我们维护 lsum,rsum 分别表示 x 子树外左侧和右侧的 siz，那么左边的 lsize=lsum+sum_{lson_x}，右侧同理。若 lsize,rsize\leq \lfloor\frac {tot}{2}\rfloor，则 x 是重心。

若 x 不是重心，则必然有一边的 size 更大，遍历向更大 size 的儿子。

要求编号最小的重心，若总点数为奇数只有一个重心不用管；若为偶数则继续按照 size 大小向下遍历。

最后，用并查集维护每个点对应连通块的重心，把原重心 fa 连向新的重心，新的重心设为根。

int findp(int x,int y) {
    split(y,x);
    int rt=n+1,lsum=0,rsum=0,tot=sum[x];
    while(x) {
        pushdown(x);
        int ls=ch[x][0],rs=ch[x][1];
        int nl=sum[ls]+lsum,nr=sum[rs]+rsum;
        if(nl<=(tot>>1)&&nr<=(tot>>1)) {
            if(tot&1) {rt=x; break;}
            else rt=min(rt,x);
        }
        if(nl>=nr) {rsum+=sum[rs]+siz[x]+1; x=ls;}
        else       {lsum+=sum[ls]+siz[x]+1; x=rs;}
    }
    splay(rt);
    return rt;
}

注意到，这道题需要维护子树信息，在 splay 上一个点的 siz 维护虚儿子的子树大小之和，sum 维护 splay 上的子树 siz 和。

这样我们在维护时就需要注意，siz 维护的虚边信息，所以在 access 改变虚边时要及时更新 siz_x。

而在 link 函数时要格外注意，由于改变了 y 的 siz 信息，如果没有向上传递信息的过程则 y 祖先都不会有信息更新。所以一定要先 makeroot(y) 省去向上传递的过程，此时 y 是根不需要向上传递信息。

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

void access(int x) {
    int z=x;
    for(int y=0;x;y=x,x=fa[x]) {
        splay(x); 
        siz[x]+=sum[ch[x][1]]-sum[y];
        ch[x][1]=y;
        pushup(x);
    }
    splay(z);
}

void link(int x,int y) {
    makeroot(x);
    makeroot(y);    //
    fa[x]=y;
    siz[y]+=sum[x];
    pushup(y);
}

::::info[code]

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define rep(i,X,Y) for (int i=(X);i<=(Y);++i)
#define per(i,X,Y) for (int i=(X);i>=(Y);--i)
#define FIO(X) freopen(#X".in","r",stdin),freopen(#X".out","w",stdout);
#define mem(X,val) memset(X,val,sizeof(X));
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define se second
#define ALL(X) X.begin(),X.end()
#define pb push_back
#define eb emplace_back
const bool MUL=false;

const int N=3e5+10;

int n,m;

int ch[N][2],fa[N],siz[N],sum[N];
bool rev[N];
int stk[N];

bool dir(int x) {return ch[fa[x]][1]==x;}
void pushup(int x) {
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+siz[x]+1;
}
void pushrev(int x) {
    swap(ch[x][0],ch[x][1]);
    rev[x]^=1;
}
void pushdown(int x) {
    if(rev[x]) {
        pushrev(ch[x][0]); pushrev(ch[x][1]);
        rev[x]=0;
    }
}
bool isroot(int x) {
    return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
void rotate(int x) {
    int y=fa[x],z=fa[y];
    bool r=dir(x);
    if(!isroot(y)) ch[z][dir(y)]=x;
    fa[x]=z;
    ch[y][r]=ch[x][!r]; if(ch[y][r]) fa[ch[y][r]]=y;
    ch[x][!r]=y; fa[y]=x;
    pushup(y); pushup(x);
}
void splay(int x) {
    int top=0,r=x;
    stk[++top]=r;
    while(!isroot(r)) r=fa[r],stk[++top]=r;
    while(top) pushdown(stk[top--]);
    while(!isroot(x)) {
        int y=fa[x];
        if(!isroot(y)) rotate(dir(y)==dir(x)?y:x);
        rotate(x);
    }
}

void access(int x) {
    int z=x;
    for(int y=0;x;y=x,x=fa[x]) {
        splay(x); 
        siz[x]+=sum[ch[x][1]]-sum[y];
        ch[x][1]=y;
        pushup(x);
    }
    splay(z);
}

void makeroot(int x) {
    access(x);
    pushrev(x);
}

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

void link(int x,int y) {
    makeroot(x);
    makeroot(y);
    fa[x]=y;
    siz[y]+=sum[x];
    pushup(y);
}

int findp(int x,int y) {
    split(y,x);
    int rt=n+1,lsum=0,rsum=0,tot=sum[x];
    while(x) {
        pushdown(x);
        int ls=ch[x][0],rs=ch[x][1];
        int nl=sum[ls]+lsum,nr=sum[rs]+rsum;
        if(nl<=(tot>>1)&&nr<=(tot>>1)) {
            if(tot&1) {rt=x; break;}
            else rt=min(rt,x);
        }
        if(nl>=nr) {rsum+=sum[rs]+siz[x]+1; x=ls;}
        else       {lsum+=sum[ls]+siz[x]+1; x=rs;}
    }
    splay(rt);
    return rt;
}

int p[N];
int find(int x) {
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}

int Solve() {
    cin>>n>>m;
    int res=0; 
    rep(i,1,n) {
        res^=i;
        p[i]=i;
        sum[i]=1;
    }
    while(m--) {
        string op; int x,y; cin>>op;
        if(op[0]=='A') {
            cin>>x>>y;
            link(x,y);
            x=find(x); y=find(y);
            int z=findp(x,y);
            res=res^x^y^z;
            p[x]=p[y]=p[z]=z;
        } else if(op[0]=='Q') {
            cin>>x;
            cout<<find(x)<<'\n';
        } else {
            cout<<res<<'\n';
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int T=1; if(MUL) cin>>T; while (T--) { Solve(); }
    return 0;
}

::::