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

点击量：274

前言

学习动态树(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;
}