动态树 Link-cut tree 【学习笔记】

作者: wjyyy 分类: LCT,学习笔记,数据结构 发布时间: 2018-12-31 11:04

点击量:60

前言

学习动态树(Link-cut Tree=LCT),首先需要掌握splay,并且可以灵活运用,因为LCT中用到了splay来维护树链。这里的splay必须维护父指针,才能有实边、虚边的区分。

链剖

重链剖分(树链剖分)

重链剖分是以dfs序的形式维护由链上指向重儿子的边所构成的链。常用线段树(或平衡树?)维护,可以查询树上简单路径上的点或边的和、最值等问题。

实链剖分

实链是在LCT中要用到的概念。树上的每一个点最多与一个儿子的连边为实边,其余的儿子为虚边。实边意味着两边都承认的边,虚边表示这条边认父不认子。因为LCT要用splay来维护,splay作为一棵二叉树,所能维护的只有每个节点的一个儿子和它的父亲(后面会提),也保证了实边的唯一;又因为树上每个点的父亲是唯一的,儿子可以有许多,因此需要通过存下每个点的父亲来维护树的形态。

对于每条实链,我们需要用一棵splay来维护。由于“树上的每一个点最多与一个儿子的连边为实边”,所以一条实链上的点的深度是唯一的。直白一点的理解就是向上爬,不拐弯

比如对于这样一棵树来说,一种可行的剖分是右侧这种。

可以分成这样几块splay:

对于每块splay,都可以抽象地当作把这条链封装起来的一个容器。容器内元素以深度为关键字严格递增,中序遍历这棵splay就可以从上到下还原出这条链。一个容器\(A\)可以挂在另一个容器\(B\)的任何一个部位,表示为\(A\)的父亲为\(B_i\)而\(B_i\)没有儿子是\(A\)。如果两个点有儿子关系,那么他们一定在同一条实链上相邻,比如\(B_{i+1}\)在原图上是\(B_i\)的儿子,那么\(B_i\)在splay中的右儿子是\(B_{i+1}\)(当且仅当处于二者以实边相连)。

LCT

LCT叫做 Link-cut Tree ,顾名思义就是可以连边和断边的树。不过它可不是一般的树,它支持在\(O(\log n)\)的时间内查询树上任意两点间最短路径上的信息。

Rotate(x)

通过旋转把\(x\)向上提一层。

图中发生变化的主要是虚线框框起来的一部分。我们只需要修改\(x\)的右儿子到\(y\)的左儿子,更新该儿子的父亲;交换\(x\),\(y\)的父子关系;把\(y\)的父亲赋给\(x\),如果指向父亲的边是实边,还要更新父亲的儿子。最后把\(x\)和\(y\)维护的信息更新,注意先更新深度大的,即可。

splay(x)

把\(x\)旋转到根。同时保持这棵splay的平衡性质。

和普通splay一样,如果\(x\)向上跳两步的方向一致,那么先转\(x\)的父亲,否则直接转\(x\)。

LCT需要翻转平衡树,因此在splay操作之前,先回溯到根,然后从上到下依次pushdown()以保证树的形态的 正确性。

access(x)

英语中access这个单词可以表示“接近/使用/获取”。

splay可以维护一条实链上的全部信息。然而如果我们需要的信息不在一条实链上怎么办呢?

access(x)可以把从\(x\)到根的路径上的边全部变为实边,而把\(x\)与其儿子的边全部变为虚边。

  1. 首先操作\(x\),\(x\)一定在它所属的splay中,让\(x\)转到splay的根,接下来断掉\(x\)的右儿子。此时\(x\)所在的splay是以\(x\)为最深点的实链。接下来处理\(x\)的父亲,由于\(x\)已经是splay的根了,这里的父亲就指的是另一棵splay中的点,也就是当前\(x\)所在实链的顶端节点在原图上的父亲。参考上图,在黄色链中若\(12\)为根,则\(12\)的父亲是\(9\),也就是\(10\)在原图上的父亲。定义\(x\)所在的splay为\(A\),\(x\)的父亲为\(y\),\(y\)所在的splay为\(B\)。
  2. 把\(y\)旋转到它所在splay的根,而此时实链的方向要切换到\(x\),原来的就不能保留。因为\(y\)的深度比\(A\)中任何一个节点都要大,所以直接把\(y\)的右儿子置为\(x\)即可。原来的实链就自动变虚了。
  3. 然后递归\(y\)的父亲,重复第\(2\)步,直到\(y\)为根。(注意不要把splay的根和树的根弄混了。

此时单方面的修改儿子对图是绝对没有影响的。

makeroot(x)

本质是使\(x\)成为整棵树中深度最小的节点。

如果我们access(x),则根到\(x\)的路径处于同一棵splay中,且根为最小元素、\(x\)为最大元素。把\(x\)旋转到splay的根,翻转splay就可以了。

因为翻转splay的过程中只是改变了实链上的顺序,并没有改变与这条链有关的虚链,因此对树的形态同样没有影响。

getroot(x)

找到\(x\)所在原树中的根。

access(x),使\(x\)和根连起来,然后splay(x),方便访问平衡树。接着就很容易找到平衡树中的最小元素了。

split(x,y)

把\((x,y)\)这条路径提取为一条实链,保存在以\(y\)为根节点的树上。

首先makeroot(x),以\(x\)为根,然后access(y)即可。为了维护树的平衡,还要splay(y)到根。此时所需的信息就存在\(y\)的\(sum\)里面。

link(x,y)

连接\((x,y)\)两个节点。若二者连通则无视。

先检验二者是否连通。makeroot(x)后,如果getroot(y)!=x,说明\(y\)此时不在\(x\)子树中,二者不连通。

要利用各函数的性质,它们不单单只是执行了该执行的命令,还改变了树的形态。

比如这里makeroot(x)之后,\(x\)在原树上就没有父亲了。联想到并查集的操作,如果把\(x\)的父亲置为\(y\),那么\(x\)子树中所有的节点就都有\(y\)这个祖先了,也就是都与\(y\)连通了。

cut(x,y)

切断\((x,y)\)两点之间的边,如果二者之间没有直接相连则无视。

同样要先检验二者是否相连。首先makeroot(x),此时\(y\)在原图上一定是\(x\)的儿子,但是在splay森林中二者不一定具有父子关系。

这时如果getroot(y)!=x,则一定不相连。而调用这个函数又相当于进行了一次access(y),splay(y),这时\(x\)和\(y\)就一定在同一条实链/splay上了。只需要判断\(x\),\(y\)是否关键字相邻就可以了,需要满足“fa[x]=y(\(y\)的左儿子是\(x\))、ch[1][x]=0(\(x\)没有右儿子)”。

然后互相切断,fa[x]=0,ch[0][y]=0,此时再maintain(y)即可。

其他

对于模板中的修改操作,可以把\(x\)直接提到当前splay的根,修改后maintain(x)就可以了。

Code:

#include<cstdio>
#include<cstring>
#define ls ch[0][k]
#define rs ch[1][k]
#define which(k) (ch[1][fa[k]]==k)
#define isroot(k) (ch[0][fa[k]]!=k&&ch[1][fa[k]]!=k)
//树的形态一旦改变 必要情况下要maintain
int key[300100],ch[2][300100],lazy[300100];
int sum[300100],fa[300100];
void pushdown(int k)
{
    if(lazy[k])
    {
        lazy[k]=0;
        lazy[ls]^=1;
        lazy[rs]^=1;
        int tmp=ls;
        ls=rs;
        rs=tmp;
    }
}
void maintain(int k)
{
    sum[k]=sum[ls]^key[k]^sum[rs];
}
void Rotate(int k)
{
    int y=fa[k];
    if(!isroot(y))//调用Rotate(k)时就保证了k不是根
        ch[which(y)][fa[y]]=k;
    bool d=which(k);

    fa[k]=fa[y];//第一步 二者互相换
    fa[y]=k;
    ch[d][y]=ch[!d][k];//第二步 只换一个儿子
    fa[ch[d][y]]=y;//更新这个儿子
    ch[!d][k]=y;//第三步 重新认儿子
    maintain(y);
    maintain(k);//第四步更新 (不更新父亲)
}
int stk[300100];
void splay(int k)//把k旋到当前树的根
{
    int x=k;
    int tp=0;
    while(!isroot(x))
    {
        stk[++tp]=x;
        x=fa[x];
    }
    stk[++tp]=x;
    while(tp)
        pushdown(stk[tp--]);//把可能影响到的位置全部下放

    while(!isroot(k))
    {
        int y=fa[k];
        if(!isroot(y))
            Rotate(which(k)^which(y)?k:y);
        Rotate(k);
    }
}
void access(int k)//把k与根连起来
{
    for(int x=k,y=0;x;y=x,x=fa[x])
    {
        splay(x);
        ch[1][x]=y;//理解
        maintain(x);
    }
}
void makeroot(int k)//使k成为根
{
    access(k);
    splay(k);
    lazy[k]^=1;
}
void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}
int getroot(int k)
{
    access(k);
    splay(k);
    while(ls)
        k=ls;
    return k;
}
void link(int x,int y)
{
    makeroot(x);
    if(getroot(y)==x)
        return;
    fa[x]=y;
}
void cut(int x,int y)
{
    makeroot(x);
    if(getroot(y)!=x||fa[x]!=y||ch[1][x])//x有右儿子也不行
        return;
    fa[x]=0;
    ch[0][y]=0;
    maintain(y);
}
int main()
{
    int n,m,op,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&key[i]);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&op,&u,&v);
        if(op==0)
        {
            split(u,v);
            printf("%d\n",sum[v]);
        }
        else if(op==1)
            link(u,v);
        else if(op==2)
            cut(u,v);
        else
        {
            access(u);
            splay(u);
            key[u]=v;
            maintain(u);
        }
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */