【学习笔记】 – 基础数据结构 ：Link-Cut Tree

Posted on by hackdl

发现树剖代码太长了，给我恶心坏了

学个代码短点的能写树剖题的数据结构吧

前置知识

  • 平衡树splay

  • 树链剖分

简介以及优缺点介绍

Link-Cut Tree，也就是LCT，一般用于解决动态树问题

Link-Cut Tree可用于实现重链剖分的绝大多数问题，复杂度为(O(n log n))，看起来比树剖的(O(n log^2 n))复杂度更小，但则不然，基于splay实现的Link-Cut Tree常数巨大(约11倍常数)，往往表现不如树剖

Link-Cut Tree的代码往往比树剖少一些

动态树问题

维护一个森林，支持删除某条边，连接某条边，并保证加边/删边之后仍是森林

同时维护这个森林的一些信息

实链剖分

  • 回顾重链剖分

    • 按子树大小剖分整棵树并重新标号

    • 此时树上形成了一些以链为单位的连续区间，用线段树进行区间操作

我们发现，诶重剖怎么是按子树大小来剖的，这也不能搞动态树啊

显然我们需要让剖分的链是我们指定的链，以便利用来求解

  • 实链剖分

    对于一个点连向它所有儿子的边，我们自己选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边。

    我们称实边所连接的儿子为实儿子，实边组成的链称之为实链

    选择实链剖分的最重要的原因便是因为实链是我们选择的，灵活且可变

    正是它的这种灵活可变性，用 Splay 来维护这些实链

Link-Cut Tree

我们可以把 LCT 理解为用一些 Splay 来维护动态树剖并实现动态树上的区间操作

每条实链都建一个 Splay 维护整个链的区间信息

  • 辅助树

    我们认为一些 Splay 共同构成了一颗辅助树，每个辅助树都维护了一颗树，所有的辅助树构成了 Link-Cut Tree，维护了整个森林

    辅助树有很多性质

    • 辅助树由多棵 Splay 组成，每棵 Splay 都维护了树中一条严格在原树中「服务器托管网从上到下」深度单调递增的路径，且中序遍历这棵 Splay 得到的点的深度序列单调递增

    • 原本的树的每个节点与辅助树的 Splay 节点一一对应。

    • 辅助树各棵 Splay 间并不独立。在 LCT 中每棵 Splay 的根节点的父亲节点指向原树中这条链的父亲节点（即链最顶端的点的父亲节点）。

      特殊的，这里的儿子认父亲，父亲却不认儿子，对应原树的一条 虚边

      故每个连通块恰好有一个点的父亲节点为空

    • 维护任何操作都不需要维护原树

      辅助树可以在任何情况下拿出一个唯一的原树

      只需维护辅助树即可

    这是一颗原树 (gets)

    这是建出的辅助树 (gets)

代码实现

这里只有 LCT 特有的几个操作

  • 数组定义

    fa[x] //x的父亲节点
son[x][2] //x的左右儿子
sz[x] //x的子树大小
rev[x] //x是否需要对儿子进行翻转

  • splay操作

    和正常splay不同的是LCT的每次splay影响的所有点都必须是当前splay中的钱

    而且在splay操作前必须把它的所有祖先全都pushdown，因为LCT不一定把哪个点应用splay操作

    • 代码

      inline bool isroot(int x){
    return ((son[fa[x]][0]==x)||(son[fa[x]][1]==x));
}
inline void splay(int x){
    int y=x,z=0;
    st[++z]=y;
    while(isroot(y)){
        st[++z]=y=fa[y];
    }
    while(z){
        push_down(st[z--]);
    }
    while(isroot(x)){
        y=fa[x],z=fa[y];
        if(isroot(y))
            rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
        rotate(x);
    }
    push_up(x);
}

  • access操作

    LCT最重要的操作，其他所有操作都要用到它

    含义是访问某节点，作用是对于访问的节点 (x) 打通一条从树根到 (x) 的实链

    如果有其他实边与新的实链相连则改为轻边

    可以理解为专门开辟一条从 (x) 到 (root) 的路径，用splay来维护这条路径

    • 实现方法

      先把 (x) 旋转到所在Splay的根

      用 (y) 记录上一次的 (x) (初始化(y=0))，把 (y) 接到 (x) 的右儿子上

      这样就把上一次的实链接到了当前实链下

      它原来的右儿子(也就是LCT树中在 (x) 下方的点)与它所有的边自然变成了虚边

      记得pushup

    • 代码

      inline void access(int x){
    for(int y=0;x;x=fa[y=x])
        splay(x),
        rc=y,push_up(x);
}

  • 换根操作

    作用是把某个节点变成树根(这里的根指的是整颗LCT的根)

    再加上access操作就能方便的提取出LCT上两点之间距离

    提取(u)到(v)的路径只需要toroot(u),access(v)，然后(v)所在的Splay对应的链就是(u)到(v)的路径

    • 实现方法

      先 access 一下，这样 (x) 就一路打通到了根，然后再splay(x)，由于x是这条实链最下面的点，所以 (x) 的 splay 的右儿子是空的，左儿子是它上面所有点

      因为 splay 是支持区间翻转的，所以只要给x打个翻转标记就翻转到根了

    • 代码

      inline void toroot(int x){
    access(x);
    splay(x);
    reserve(x);
}

  • link操作

    作用是链接两个辅助树，对于link(u,v)，表示 (u) 所在的辅助树和 (v) 所在的辅助树

    • 实现方法

      只需要先toroot(u)，然后记 fa[u]=v 就可以了，就是把一整颗辅助树连到另一个点上

    • 代码

      inline void link(int x,int y){
    toroot(x);
    if(Find(y)!=x)
        fa[x]=y;
}

  • cut操作

    这个操作作用是切断某条边

    • 实现方法

      先分离出 (x) 到 (y) 的这条链

      我们假设切断的点一定是相邻的(不相邻的特判掉)，然后把 (y) 的左儿子(也就是 LCT 中 (y) 的父亲)与 (y) 的边断掉就好了

    • 代码

      inline void split(int x,int y){
    toroot(x);
    access(y);
    splay(y);
}
inline int Find(int x){
    access(x);
    splay(x);
    while(lc)
        push_down(x),x=lc;
    splay(x);
    return x;
}
inline void cut(int x,int y){
    toroot(x);
    if(Find(y)==x&&fa[y]==x&&!son[y][0]){
        fa[y]=son[x][1]=0;
        push_up(x);
    }
}

完整代码

模板题

点击查看代码 
#define lc son[x][0]
#define rc son[x][1]
int fa[N],son[N][2],val[N],ans[N],st[N];
bool rev[N];
inline bool isroot(int x){
    return ((son[fa[x]][0]==x)||(son[fa[x]][1]==x));
}
inline void push_up(int x){
    ans[x]=ans[lc]^ans[rc]^val[x];
}
inline void reserve(int x){
    int t=lc;
    lc=rc;rc=t;
    rev[x]^=1;
}
inline void push_down(int x){
    if(rev[x]){
        if(lc)reserve(lc);
        if(rc)reserve(rc);
        rev[x]=0;
    }
}
inline void rotate(int x){
    int y=fa[x],z=fa[y],k=son[y][1]==x,w=son[x][!k];
    if(isroot(y))
        son[z][son[z][1]==y]=x;
    son[x][!k]=y;
    son[y][k]=w;
    if(w)
        fa[w]=y;
    fa[y]=x;fa[x]=z;
    push_up(y);
}
inline void splay(int x){
    int y=x,z=0;
    st[++z]=y;
    while(isroot(y)){
       服务器托管网 st[++z]=y=fa[y];
    }
    while(z){
        push_down(st[z--]);
    }
    while(isroot(x)){
        y=fa[x],z=fa[y];
        if(isroot(y))
            rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
        rotate(x);
    }
    push_up(x);
}
inline void access(int x){
    for(int y=0;x;x=fa[y=x])
        splay(x),
        rc=y,push_up(x);
}
inline void toroot(int x){
    access(x);
    splay(x);
    reserve(x);
}
inline int Find(int x){
    access(x);
    splay(x);
    while(lc)
        push_down(x),x=lc;
    splay(x);
    return x;
}
inline void split(int x,int y){
    toroot(x);
    access(y);
    splay(y);
}
inline void link(int x,int y){
    toroot(x);
    if(Find(y)!=x)
        fa[x]=y;
}
inline void cut(int x,int y){
    toroot(x);
    if(Find(y)==x&&fa[y]==x&&!son[y][0]){
        fa[y]=son[x][1]=0;
        push_up(x);
    }
}
signed main(){
    int n,m;FastI>>n>>m;
    for(int i=1;i>val[i];
    while(m--){
        int opt,x,y;
        FastI>>opt>>x>>y;
        if(opt==0){
            split(x,y);
            FastO

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 软件确认过程

服务器托管，北京服务器服务器托管网托管，服务器租用 http://www服务器托管网.fwqtg.net 机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net相关推荐: java jna 动态库从资源路径载入问题？在其他项目中依赖…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: