学习心得 - 数据结构 - LCT

ExFish · 2025-02-19 20:06:35 · 算法·理论

什么是 LCT

LCT（Link-Cut-Tree）是一种用于解决动态树问题的算法。

比如说我们需要维护一颗有边权的树：

维护路径权值和。
修改路径上权值。
修改子树边权。
查询子树边权和。
断开一条边保证还是树。

前四个可以轻松用树链剖分维护。

但是最后一个问题的出现，让问题变成了动态树问题，考虑使用 LCT 维护。

注意到这个动态树问题是维护一个森林。

树链剖分一般是使用重链剖分。

而这里，我们考虑使用实链剖分。

实链剖分

我们对一个节点连向儿子的边称为实边，其他边称为轻边。注意到这个边是可以变的。

LCT

我们可以把 LCT 理解成用 Splay 维护一个实链剖分。

对于每一条实链，我们都用一颗 Splay 来维护链上答案。

辅助树

把这些 Splay 编成一个树，叫做辅助树。

我们可以从这颗树中找到原树。

具体的，辅助树中的 Splay 根节点指向原树父节点。

我们发现这个东西其实就是一堆 Splay 用虚边连接，我觉得很像重链和重链之间由轻边连接，这里则是实链和实链之间由虚边连接。

原树实链：处于一颗辅助树 Splay 中。
原树虚边：在 Splay 中根的父节点所在链中。

注意到辅助树可以任意换根。

还有就是实链虚链变换是可以很轻松地完成。

LCT 函数

pushup，更新子树。（辅助树）
pushdown，下放标记。（辅助树）
gets，获取一个点是父亲的哪个儿子。（Splay）
splay，旋转到 p 点（Rotate）。（Splay）
Rotate，树旋。（Splay）
access，重要操作，把根到 p 的路径划分到一条实链里。（LCT）
isroot，判定是否是所在树的根。（LCT）
update，在 access 后 pushdown 更新信息。（LCT）
mroot，让 p 成为根。（LCT）
link 连边。（LCT）
cut 删边。（LCT）
find，找到根节点编号。（LCT）
fix，修改点权值。（LCT）
split，提取区间路径操作。（LCT）

代码

~~咕咕咕咕咕咕。~~

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int n,q,U,V,UU,VV,C;
int op;
struct node{
    int siz,son[2],fa,val,sum,rev,add,mul;
}a[N];
void clear(int p){
    a[p].son[0]=0;
    a[p].son[1]=0;
    a[p].fa=0;
    a[p].siz=0;
    a[p].val=0;
    a[p].sum=0;
    a[p].rev=0;
}
void pushup(int p){
    a[p].siz=a[a[p].son[0]].siz+a[a[p].son[1]].siz+1;
    a[p].sum=a[a[p].son[0]].sum^a[a[p].son[1]].sum^a[p].val;
}
void pushdown(int p){
    clear(0);
    if(a[p].rev!=0){
        if(a[p].son[0]){
            a[a[p].son[0]].rev^=1;
            swap(a[a[p].son[0]].son[0],a[a[p].son[0]].son[1]);
        }
        if(a[p].son[1]){
            a[a[p].son[1]].rev^=1;
            swap(a[a[p].son[1]].son[0],a[a[p].son[1]].son[1]);
        }
        a[p].rev=0;
    }
}
int gets(int p){
    return a[a[p].fa].son[1]==p;
}
int isroot(int p){
    clear(0);
    return(a[a[p].fa].son[0]!=p&&a[a[p].fa].son[1]!=p);
}
void update(int p){
    if(!isroot(p))update(a[p].fa);
    pushdown(p);
}
void rotate(int p){
    int q=a[p].fa,r=a[q].fa,k=gets(p),kk=gets(q);
    a[p].fa=r;
    if(!isroot(q))a[r].son[kk]=p;
    a[q].son[k]=a[p].son[!k];
    a[a[p].son[!k]].fa=q;
    a[p].son[!k]=q;
    a[q].fa=p;
    pushup(q),pushup(p),pushup(r);
}
void splay(int p){
    update(p);
    for(int f;f=a[p].fa,!isroot(p);rotate(p)){
        if(!isroot(f))rotate(gets(f)==gets(p)?f:p);
    }
}
void access(int x){
    int p;
    for(p=0;x;p=x,x=a[x].fa){
        splay(x);a[x].son[1]=p;pushup(x);
    }
}
void mroot(int p){
    access(p);
    splay(p);
    swap(a[p].son[0],a[p].son[1]);
    a[p].rev^=1;
}
void split(int x,int y){
    mroot(x);
    access(y);
    splay(y);
}
void cut(int x,int p){
    split(x,p);
    if(a[p].son[0]==x&&!a[x].son[1])a[p].son[0]=a[x].fa=0;
}
int find(int p){
    access(p);
    splay(p);
    while(a[p].son[0])p=a[p].son[0];
    splay(p);
    return p;
}
void link(int x,int p){
    if(find(x)==find(p))return;
    mroot(x);
    a[x].fa=p;
}
void print(int p){
    if(!p)return;
    pushdown(p);
    print(a[p].son[0]);
    cout<<p<<" ";
    print(a[p].son[1]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i].val,pushup(i);
    while(q--){
        cin>>op;
        if(op==0){
            cin>>U>>V;
            split(U,V);
            cout<<a[V].sum<<"\n";
        }else if(op==1){
            cin>>U>>V;
            link(U,V);
        }else if(op==2){
            cin>>U>>V;
            cut(U,V);
        }else if(op==3){
            cin>>U>>V;
            splay(U);
            a[U].val=V;
            pushup(U);
        }
    }
    return 0;
}