动态树 — Link_Cut_Tree
阅读原文时间:2023年07月08日阅读:1

Link-cut-tree是一种维护动态森林的数据结构,在需要动态加边/删边的时候就需要LCT来维护。

Link-cut-tree的核心是轻重链划分,每条重链用一颗splay来维护。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct LCT{
    int son[2][100005],fa[100005],siz[100005],val[100005];
    inline void pushup(int x){siz[x]=siz[son[0][x]]^siz[son[1][x]]^val[x];}
    bool rev[100005];
    inline void pushdown(int x){
        if(!rev[x])return ;
        rev[son[0][x]]^=1;rev[son[1][x]]^=1;
        swap(son[0][x],son[1][x]);rev[x]=0;
    }
    inline bool isroot(int x){
        return !(son[0][fa[x]]==x||son[1][fa[x]]==x);
    }
    inline void rotate(int x){
        int y=fa[x],z=fa[y];
        if(!isroot(y))son[y==son[1][z]][z]=x;
        bool is=(son[1][y]==x);
        son[is][y]=son[!is][x];fa[son[!is][x]]=y;
        son[!is][x]=y;fa[y]=x;fa[x]=z;pushup(y);pushup(x);
    }
    int stk[100005],top;
    inline void splay(int x){
        stk[++top]=x;
        for(int i=x;!isroot(i);i=fa[i])stk[++top]=fa[i];
         while(top)pushdown(stk[top--]);
        while(!isroot(x)){
            int y=fa[x],z=fa[y];//cout<<x<<" "<<y<<" "<<z<<endl;
            if(!isroot(y)){
                if((son[1][y]==x)^(son[1][z]==y))rotate(x);
                else rotate(y);
            }rotate(x);
        }
    }
    inline void access(int x){
        for(int i=0;x;i=x,x=fa[x])splay(x),son[1][x]=i,pushup(x);
    }
    inline void makert(int x){
        access(x);splay(x);rev[x]^=1;
    }
    inline int find(int x){
        access(x);splay(x);while(son[0][x])x=son[0][x];
        return x;
    }
    inline void link(int x,int y){
        if(find(x)==find(y))return ;
        makert(x);fa[x]=y;
    }
    inline void split(int x,int y){
        makert(x);access(y);splay(y);
    }
    inline void cut(int x,int y){
        split(x,y);
        if(son[0][y]==x&&son[1][x]==0)son[0][y]=fa[x]=0;
    }
}T;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&T.val[i]),T.siz[i]=T.val[i];
    while(m--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==0)T.split(x,y),printf("%d\n",T.siz[y]);
        if(op==1)T.link(x,y);
        if(op==2)T.cut(x,y);
        if(op==3)T.makert(x),T.val[x]=y,T.pushup(x);
    }

    return 0;
} 

【模板】最近公共祖先(LCA)

\(LCT\) 也是一种求 \(lca\) 的方法法,而且好像比倍增快

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int son[2][500005],fa[500005];
bool rev[500005];
inline void down(int x){
    if(rev[x]){
        swap(son[0][x],son[1][x]);
        rev[son[0][x]]^=1;rev[son[1][x]]^=1;
    }rev[x]=0;
}
inline bool isroot(int x){
    return son[1][fa[x]]!=x&&son[0][fa[x]]!=x;
}
inline void rotate(int x){
    int y=fa[x],z=fa[y];
    if(!isroot(y))son[y==son[1][z]][z]=x;
    bool is=(son[1][y]==x);
    son[is][y]=son[!is][x];fa[son[!is][x]]=y;
    son[!is][x]=y;fa[x]=z;fa[y]=x;
}
int stk[500005],top;
inline void splay(int x){
    stk[++top]=x;
    for(int y=x;!isroot(y);y=fa[y])stk[++top]=fa[y];
    while(top)down(stk[top--]);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)){
            if((son[1][y]==x)^(son[1][z]==y))rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
inline int access(int x){
    int i=0;
    for(;x;i=x,x=fa[x])splay(x),son[1][x]=i;
    return i;
}
inline void makert(int x){
    access(x);splay(x);rev[x]^=1;
}
inline void link(int x,int y){
    makert(x);fa[x]=y;
}
inline void split(int x,int y){
    makert(x);access(y);splay(y);
}
inline void cut(int x,int y){
    split(x,y);son[0][y]=fa[x]=0;
}
inline int find(int x){
    access(x);splay(x);while(son[0][x])x=son[0][x];
    return x;
}
inline int lca(int x,int y){
    access(x);splay(x);
    return access(y);
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    son[0][0]=son[1][0]=-1;
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        link(x,y);
    }makert(s);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }

    return 0;
} 

[SDOI2008] 洞穴勘测

又是一个模板,不过好像可以暴力水过去

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int son[2][10005],fa[10005];
bool rev[10005];
inline void down(int x){
    if(rev[x]){
        swap(son[0][x],son[1][x]);
        rev[son[0][x]]^=1;rev[son[1][x]]^=1;
    }rev[x]=0;
}
inline bool isroot(int x){
    return son[1][fa[x]]!=x&&son[0][fa[x]]!=x;
}
inline void rotate(int x){
    int y=fa[x],z=fa[y];
    if(!isroot(y))son[y==son[1][z]][z]=x;
    bool is=(son[1][y]==x);
    son[is][y]=son[!is][x];fa[son[!is][x]]=y;
    son[!is][x]=y;fa[x]=z;fa[y]=x;
}
int stk[10005],top;
inline void splay(int x){
    stk[++top]=x;
    for(int y=x;!isroot(y);y=fa[y])stk[++top]=fa[y];
    while(top)down(stk[top--]);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)){
            if((son[1][y]==x)^(son[1][z]==y))rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
inline void access(int x){
    for(int i=0;x;i=x,x=fa[x])splay(x),son[1][x]=i;
}
inline void makert(int x){
    access(x);splay(x);rev[x]^=1;
}
inline void link(int x,int y){
    makert(x);fa[x]=y;
}
inline void split(int x,int y){
    makert(x);access(y);splay(y);
}
inline void cut(int x,int y){
    split(x,y);son[0][y]=fa[x]=0;
}
inline int find(int x){
    access(x);splay(x);while(son[0][x])x=son[0][x];
    return x;
}
char op[15];
int main(){
    scanf("%d%d",&n,&m);
    son[0][0]=son[1][0]=-1;
    while(m--){
        int x,y;
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='Q')puts(find(x)==find(y)?"Yes":"No");
        if(op[0]=='C')link(x,y);
        if(op[0]=='D')cut(x,y);
    }

    return 0;
} 

[NOI2014] 魔法森林

\(LCT\) 想维护边上信息,只需对每条边开一个点出来即可

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int son[2][200005],fa[200005];
bool rev[200005];
struct node{
    int x,y,a,b,id;
    node(){}
    node(int _x,int _y,int _a,int _b,int _id){
        x=_x;y=_y;a=_a;b=_b;id=_id;
    }
    inline bool operator <(const node &b)const{
        return a<b.a;
    }
}val[200005],sm[200005];
inline node cmp(node x,node y){
    return x.b<y.b?y:x;
}
inline void pushup(int x){
    sm[x]=val[x];
    sm[x]=cmp(sm[x],sm[son[0][x]]);
    sm[x]=cmp(sm[x],sm[son[1][x]]);
}
inline void down(int x){
    if(rev[x]){
        swap(son[0][x],son[1][x]);
        rev[son[0][x]]^=1;rev[son[1][x]]^=1;
    }rev[x]=0;
}
inline bool isroot(int x){
    return son[0][fa[x]]!=x&&son[1][fa[x]]!=x;
}
inline void rotate(int x){
    int y=fa[x],z=fa[y];
    if(!isroot(y))son[son[1][z]==y][z]=x;
    bool is=(son[1][y]==x);
    son[is][y]=son[!is][x];fa[son[!is][x]]=y;
    son[!is][x]=y;fa[x]=z;fa[y]=x;pushup(y);pushup(x);
}
int stk[200005],top;
inline void splay(int x){
    stk[++top]=x;
    for(int i=x;!isroot(i);i=fa[i])stk[++top]=fa[i];
    while(top)down(stk[top--]);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)){
            if((son[1][y]==x)^(son[1][z]==y))rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
inline void access(int x){
    for(int i=0;x;i=x,x=fa[x])splay(x),son[1][x]=i,pushup(x);
}
inline void makert(int x){
    access(x);splay(x);rev[x]^=1;
}
inline void link(int x,int y){
    makert(x);splay(x);fa[x]=y;
}
inline void cut(int x,int y){
    makert(x);splay(x);access(y);splay(y);
    son[0][y]=fa[x]=0;pushup(y);
}
inline node select(int x,int y){
    makert(x);splay(x);access(y);splay(y);
    return sm[y];
}
inline int find(int x){
    access(x);splay(x);for(down(x);son[0][x];down(x))x=son[0][x];
    return x;
}
vector<node> vec;
int ans=2e9;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,a,b;
        scanf("%d%d%d%d",&x,&y,&a,&b);if(x==y)continue;
        val[n+i]=node(x,y,a,b,i+n);vec.push_back(val[n+i]);
    }son[0][0]=son[1][0]=-1;
    sort(vec.begin(),vec.end());
    for(auto it:vec){
        if(find(it.x)!=find(it.y))link(it.id,it.x),link(it.id,it.y);
        else {
            node u=select(it.x,it.y);
            if(u.b>it.b){
                cut(u.x,u.id);cut(u.y,u.id);
                link(it.x,it.id);link(it.y,it.id);
            }
        }
        if(find(1)==find(n)){
            ans=min(ans,it.a+select(1,n).b);
        }
    }
    printf("%d",ans==2e9?-1:ans);

    return 0;
} 

[BJOI2014]大融合

把 \(access\) 改一下,再注意一下更新时 \(splay\) 的形态,就可以用\(LCT\) 维护虚子树信息

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
int son[2][100005],fa[100005],siz[100005],val[100005];
bool rev[100005];
inline void pushup(int x){
    siz[x]=siz[son[0][x]]+val[x]+siz[son[1][x]];
}
inline void down(int x){
    if(rev[x]){
        swap(son[0][x],son[1][x]);
        rev[son[0][x]]^=1;rev[son[1][x]]^=1;
    }rev[x]=0;
}
inline bool isroot(int x){
    return son[1][fa[x]]!=x&&son[0][fa[x]]!=x;
}
inline void rotate(int x){
    int y=fa[x],z=fa[y];
    if(!isroot(y))son[son[1][z]==y][z]=x;
    bool is=(son[1][y]==x);
    son[is][y]=son[!is][x];fa[son[!is][x]]=y;
    son[!is][x]=y;fa[x]=z;fa[y]=x;pushup(y);pushup(x);
}
int stk[100005],top;
inline void splay(int x){
    stk[++top]=x;
    for(int i=x;!isroot(i);i=fa[i])stk[++top]=fa[i];
    while(top)down(stk[top--]);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)){
            if((son[1][y]==x)^(son[1][z]==y))rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
inline void access(int x){
    for(int i=0;x;i=x,x=fa[x]){
        splay(x);val[x]+=siz[son[1][x]];
        son[1][x]=i;val[x]-=siz[i];pushup(x);
    }
}
inline void makert(int x){
    access(x);splay(x);rev[x]^=1;
}
inline void link(int x,int y){
    makert(x);makert(y);fa[x]=y;
    val[y]+=siz[x];pushup(y);
}
inline void cut(int x,int y){
    makert(x);access(y);splay(y);
    son[0][y]=fa[x]=0;pushup(x);pushup(y);(x);makert(y);
}
inline int query(int x){
    access(x);splay(x);
    return siz[x];
}
char op[2];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)siz[i]=val[i]=1;
    while(q--){
        int x,y;
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='A')link(x,y);
        else {
            cut(y,x);
            printf("%lld\n",1ll*query(x)*query(y));
            link(x,y);
        }
    }

    return 0;
} 

【模板】 "动态DP"&动态树分治(加强版)

对于静态树,可以将 \(splay\) 静态化为一颗普通 \(BST\) ,称为 “全局平衡二叉树”

点击查看代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
using namespace std;
int n,m;
const int SIZE=(1<<21)+1;
char ibuf[SIZE],*iS=ibuf,*iT=ibuf;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
template <class T>
void read(T &x){
    int f=0;x=0;char c=gc();
    while(!isdigit(c)) f|=c=='-',c=gc();
    while(isdigit(c)) x=x*10+c-'0',c=gc();
    if(f) x=-x;
}
int ver[2000005],ne[2000005],head[1000005],cnt;
inline void link(int x,int y){
    ver[++cnt]=y;
    ne[cnt]=head[x];
    head[x]=cnt;
}
int siz[1000005],son[1000005];
void dfs(int x,int fi){
    siz[x]=1;
    for(int i=head[x];i;i=ne[i]){
        int u=ver[i];
        if(u==fi)continue;
        dfs(u,x);siz[x]+=siz[u];
        if(siz[u]>siz[son[x]])son[x]=u;
    }
}
struct mat{
    int a[2][2];
    mat(int _x=0,int _y=0){a[0][0]=a[1][1]=_x;a[0][1]=a[1][0]=_y;}
    inline int* operator [](int t){
        return a[t];
    }
    inline mat operator *(mat &b){
        mat res(-1e9,-1e9);
        for(int i=0;i<2;i++){
            for(int t=0;t<2;t++){
                for(int j=0;j<2;j++)res[i][j]=max(res[i][j],a[i][t]+b[t][j]);
            }
        }return res;
    }
    inline mat operator +(mat &b){
        mat res=*this;int tmp=max(b[0][0],b[1][0]);
        res[0][0]+=tmp;res[0][1]+=tmp;res[1][0]+=b[0][0];
        return res;
    }
    inline mat operator -(mat &b){
        mat res=*this;int tmp=max(b[0][0],b[1][0]);
        res[0][0]-=tmp;res[0][1]-=tmp;res[1][0]-=b[0][0];
        return res;
    }
}val[1000005],tree[1000005];
int le[1000005],ri[1000005],stk[1000005],top;
inline void pushup(int x){
    tree[x]=tree[le[x]]*val[x]*tree[ri[x]];
}
int fa[1000005];
int build(int x,int l,int r){
    int all=0,sum=0;
    for(int i=l;i<=r;i++)all+=siz[stk[i]]-siz[son[stk[i]]];
    for(int i=l;i<=r;i++){
        sum+=siz[stk[i]]-siz[son[stk[i]]];
        if(sum>=all/2){
            le[stk[i]]=build(stk[i],l,i-1);ri[stk[i]]=build(stk[i],i+1,r);fa[stk[i]]=x;
            pushup(stk[i]);return stk[i];
        }
    }return 0;
}
bool vis[1000005];
int solve(int x,int fi=0){
    for(int y=x;y;y=son[y])vis[y]=1;
    for(int y=x;y;y=son[y]){
        for(int i=head[y];i;i=ne[i]){
            int u=ver[i];
            if(!vis[u]){
                int z=solve(u,y);
                val[y]=val[y]+tree[z];
            }
        }
    }top=0;
    for(int y=x;y;y=son[y])stk[++top]=y;
    return build(fi,1,top);
}
int a[1000005];
inline bool isroot(int x){
    return le[fa[x]]!=x&&ri[fa[x]]!=x;
}
inline void update(int x,int y){
    val[x][1][0]+=y-a[x];a[x]=y;
    while(x){
        if(isroot(x)&&fa[x])val[fa[x]]=val[fa[x]]-tree[x];
        pushup(x);
        if(isroot(x)&&fa[x])val[fa[x]]=val[fa[x]]+tree[x];
        x=fa[x];
    }
}
int ans,rt;
int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<n;i++){
        int x,y;read(x);read(y);
        link(x,y);link(y,x);
    }
    dfs(1,1);
    val[0]=tree[0]=mat(0,-1e9);
    for(int i=1;i<=n;i++){
        val[i][1][0]=a[i];
        val[i][1][1]=-1e9;
    }rt=solve(1,0);
    while(m--){
        int x,y;read(x);read(y);x^=ans;
        update(x,y);
        printf("%d\n",ans=max(tree[rt][0][0],tree[rt][1][0]));
    }

    return 0;
} 

#1220. 地平线

由于 \(splay\) 有均摊分析,最好每访问一个节点就 \(splay\) 一次,而不是只 \(splay\) 需要变为根的节点,保证复杂度

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,m,q,cnt;
int mpx[3000005],mpy[3000005];
int son[2][3000005],fa[3000005];
inline bool isroot(int x){
    return son[0][fa[x]]!=x&&son[1][fa[x]]!=x;
}
inline void rotate(int x){
    int y=fa[x],z=fa[y];
    if(!isroot(y))son[son[1][z]==y][z]=x;
    bool is=(son[1][y]==x);
    son[is][y]=son[!is][x];fa[son[is][y]]=y;
    son[!is][x]=y;fa[y]=x;fa[x]=z;
}
inline void splay(int x){
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)){
            if((son[1][y]==x)^(son[1][z]==y))rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
inline void access(int x){
    for(int i=0;x;i=x,x=fa[x])splay(x),son[1][x]=i;
}
inline void cut(int x){
    access(x);splay(x);fa[son[0][x]]=0;son[0][x]=0;
}
inline int findrt(int x){
    access(x);splay(x);
    while(son[0][x])x=son[0][x];splay(x);
    return x;
}
inline void link(int x,int y){
//    cout<<"link ("<<mpx[x]<<" "<<mpy[x]<<") ("<<mpx[y]<<" "<<mpy[y]<<")\n";
    access(x);splay(x);fa[x]=y;
}
int dsu[3000005];
inline void update(int x,int y){
    int F=findrt(x);cut(x);
    if(dsu[F]&&findrt(dsu[F])!=F)link(F,dsu[F]);
    dsu[x]=y;
    if(findrt(y)!=x)link(x,y);
}
vector<int> mp[1000005];
char s[1000005],op[3];
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=0;i<=n+1;i++){
        mp[i].resize(m+2);
        for(int j=0;j<=m+1;j++){
            mp[i][j]=++cnt;
            if(i==0||i==n+1||j==0||j==m+1)mpx[cnt]=i,mpy[cnt]=j;
            else mpx[cnt]=-1,mpy[cnt]=-1;
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            if(s[j]=='>')update(mp[i][j],mp[i][j+1]);
            else if(s[j]=='<')update(mp[i][j],mp[i][j-1]);
            else update(mp[i][j],mp[i-1][j]);
        }
    }
    while(q--){
        int x,y;char c[2];
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='q'){
            int F=findrt(mp[x][y]);
            printf("%d %d\n",mpx[F],mpy[F]);
        }else {
            scanf("%s",c);
            if(c[0]=='>')update(mp[x][y],mp[x][y+1]);
            else if(c[0]=='<')update(mp[x][y],mp[x][y-1]);
            else if(c[0]=='^')update(mp[x][y],mp[x-1][y]);
        }
    }

    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器