动态树学习总结

Asrit · 2021-10-29 10:26:35 · 个人记录

动态树的介绍

动态树，简称LCT(Link\ Cut\ Tree)

百度上对动态树给出的定义如下：

动态树问题, 即要求我们维护一个由若干棵子结点无序的有根树组成的森林，支持对树的分割, 合并, 对某个点到它的根的路径的某些操作, 以及对某个点的子树进行的某些操作。

动态树擅长的问题是动态维护树的形态（名为动态树的原因所在）、对森林进行维护、在树上进行路径的修改和维护，处理这些的复杂度为均摊O(logn)。

（可惜LCT的常数太大，当树为静态时实际运行起来比O(log^2n)的树链剖分还慢一点，但是减小常数的方法也是有的，后面也会讲。）

当然动态树还可以做的事情有很多，我们先从简单的开始入手，一步步深入LCT。

注：学习LCT前需要学会Splay。学过树链剖分的话理解LCT会轻松一点，没有学过的话影响也不大（我在学LCT前树链剖分就已经忘干净了QAQ）。

动态树的实现与基本操作

虚边与实边

类似于树链剖分用轻链和重链维护树的形态，动态树是通过虚边和实边对树的形态进行存储的，一个节点至多有1条连接儿子的实边，如图：

（这张图中1号节点为根节点）

图中红色的实线表示实边，蓝色的虚线表示虚边。

那在程序中实边与虚边怎么区分呢？

实边：儿子能直接找到通过实边连接的父亲，且父亲也能直接找到通过实边连接的儿子。

虚边：儿子能直接找到通过虚边连接的父亲，但父亲不能直接找到通过虚边连接的儿子（认父不认子）。

我们用fa[x]表示x节点的父亲，son[x]表示x节点的儿子，在图中，fa[2]=1，fa[3]=1，fa[4]=1，son[1]=2。

树链剖分的轻重链是根据子树的大小确定的，它是固定的。而动态树的虚实边是可以任意任命的，它是不固定的。因此，我们可以改变一条边的虚实。

比如说，我们把2号节点连向6号节点的边变虚，连向7号节点的边变实，那我们需要改变那些信息呢？

通过思考和图片，我们可以发现，我们只需要把son[2]改为6。

因此，当我们要将一条边改为实边时，只需要将父节点的儿子改为这条边连接的子节点。

链上信息维护

类似于树链剖分，在划分完虚边与实边后，整棵树被分成了一条条由实边连接而成的链（即实链）。

为了快速维护实链上的信息，我们使用Splay来维护实链的信息，Splay的中序遍历为链的形态，中序遍历越靠前的点越靠近父节点。

如图，

先把刚才的图的虚实边修改一下成为这个样子：

然后我们拿出4-8-11这条链并将其放入一棵Splay中：

（对于Splay中的节点x，我们用tr[x]结构体进行存储，tr[x].p表示x节点的父亲，tr[x].s[0]表示x节点的左儿子，tr[x].s[1]表示x节点的右儿子）

我们会发现，Splay的形态和父子关系跟原树差别很大，所以我们在处理过程中一定要牢记我们是在Splay中进行操作的，不要跟原树搞混！

如果我们像上图一样维护Splay的话，我们会发现：原树中有一个信息为fa[4]=1（原树中虚边的信息），而在Splay中没有体现出来。

原树中链的顶端——4号节点——在Splay中有父节点8，如果我们直接令Splay中4号点的父亲为1，那么Splay的形态会发生改变，我们所维护的也就不是这条链了。

那我们该怎么办呢？

统观整棵Splay，我们会发现Splay的根节点——8号节点——父亲信息是空的，我们可以在8号节点存下链的顶端的父亲——1号节点。

所以，我们在Splay的根节点，保存原树中链的顶端的父节点。

修改后，这棵Splay实际张这个样子：

在Splay操作中，我们经常需要找到根节点进行一些判定跟操作。只有一棵Splay时，我们通常使用一个root变量来记录根节点的信息。而在LCT中，我们有好多好多的实链，也就要维护好多好多个Splay，那我们需要逐一记录root吗？

答案是不用的。我们可以通过一个方法判断出一个点是否是Splay的根节点。

(每个绿色框内为一棵Splay，黄色边为虚边)

由于Splay的根节点的父亲存的是虚边的父节点，根据之前提到的虚边认父不认子，Splay的根节点的父亲的任何一个子节点都不会是这个根节点。

例如，tr[8].p=1，tr[1].s[0]=2，tr[1].s[1]=0

再例如，tr[5].p=2，tr[5].s[0]=0，tr[2].s[1]=0

其他的根节点同理。

因此，判断一个点是否是Splay中的根节点，只需要看在Splay中该节点的父亲的两个儿子是否都不为该节点即可。

基本操作

存储\textbf{Splay}的结构体（不知道该放哪就放在这了）

struct node{
    int s[2];//s[0]左儿子，s[1]右儿子
    int p;//父亲
    int rev;//翻转标记
    //这三个是必须有的，用于维护Splay的形态（rev标记在一般的LCT中都需要）。
    //其他需要维护的信息具体问题具体分析。
    //常见的有v(节点的权值),sum(自己和子树的权值和),sz（自己和子树的节点个数）等。
}tr[N];

\textbf{push\_up(x)},\textbf{push\_down(x)}

作用：上传更新信息和下传标记，具体问题具体分析。

\textbf{push\_rev(x)}

作用：将x及其子节点们存储的中序遍历翻转。

实现：思想与Splay的翻转相同，交换左右儿子，并下放rev标记。（注：我们的标记为1时表示左右儿子已经翻转。）

代码：

void push_rev(int x){
    swap(tr[x].s[0],tr[x].s[1]);
    tr[x].rev^=1;
}

\textbf{isroot(x})

作用：判断x节点是否是Splay中的根节点。

实现：通过判断x的父亲的儿子是否都不是x（这样判断的原因在上面讲过）。

代码：

bool isroot(int x){
    return tr[tr[x].p].s[0]!=x&&tr[tr[x].p].s[1]!=x;
}

\textbf{rotate(x)}

作用：进行一次翻转。

实现：基本同Splay，但是有一点不同：x的祖先可能不在这棵Splay中，在Splay模板中，这个点是0，修改它的左/右儿子不会造成影响；LCT中的这个点就可能是存在于别的Splay中的节点了，如果进行修改会导致Splay被破坏，因此我们需要判断一下。

代码：

void rotate(int x){
    int y=tr[x].p,z=tr[y].p,k=tr[y].s[1]==x;
    if(!isroot(y)) tr[z].s[tr[z].s[1]==y]=x;//在这里特判
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    push_up(y),push_up(x);//旋转后要自下而上更新一下信息（此时y在x的下方）
}

\textbf{push\_all(x)}

作用：将x到它所在的Splay的根节点的所有节点的标记全部下传。

实现：从x递归找当前节点的父亲，直到当前节点为根节点，然后递归返回时下传标记。

代码：

void push_all(int x){
    if(!isroot(x)) push_all(tr[x].p);
    push_down(x);
}

\textbf{splay(x)}

作用：将x节点转到它所在Splay的根节点。

实现：先将标记全部下传，再进行旋转。旋转同Splay模板（但是判断是否为根的部分需要修改）。

代码：

void splay(int x){
    push_all(x);
    for(;!isroot(x);rotate(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)) rotate((tr[z].s[1]==y)^(tr[y].s[1]==x)?x:y);
    }
}

\textbf{access(x)}(\textbf{LCT}的核心操作)

作用：打通一条从x到原树的根节点的路径（不包含路径外的节点）。

实现：

我们拿这张图来举例子。

我们来access(8)。

此时原树的根节点为1，所以我们要打通从8到1的路径。

我们考虑从8号节点一步步往上打通。

首先，我们要保证这条路径是不包含其他点的，所以我们将原树中8与11之间连的实边变成虚边。

对应的，我们需要在Splay把8和它的子节点们分开（目前子节点只有11）。当我们把8转到Splay的根后，它的右儿子就都是它的后代。所以，我们将8先转到Splay的根，然后将它的右儿子改为0，这样就分开了（根据认父不认子，只让父亲不认儿子就能分开）。

修改这一步后变成了这样：

下一步，我们将原树中4和8之间的边改为实边，并将原树中4和9之间的边改为虚边。我们将4的儿子从9改成8，就可以完成操作了。

对应在Splay中，我们要把4转到根，此时4的右儿子就对应的是它的后代们。我们将4的右儿子修改为含有8的Splay的根节点（由于上一步的旋转操作，目前该Splay根是8）就修改完成了。

现在是这个样子：

最后，我们以相同的方法，将1和4连起来。

这样，我们便打通了从8到根的路径。

边界判定为当前处理的节点是否为0（因为原树的根节点在原树以及Splay中的父亲都是0）。

（这个例子中没有包含打通路径时某个父节点所在Splay中含有多个在路径中的点的情况。如果您想要体会一下，请以我讲access时的第一张图为原树，手玩一下access(10)的情况。）

代码：

void access(int x){
    for(int y=0;x;y=x,x=tr[x].p){//y=0的原因是开始时右儿子应设为空,之后y为上一次操作后的根节点。
        splay(x);//将x转到根
        tr[x].s[1]=y;//上次操作的根为现在点的右儿子
        push_up(x);//更新信息
    }
}

\textbf{makeroot(x)}

作用：把x改为原树的根。

实现：

打通x到根的路径，然后将整棵Splay翻转。

这样操作的原因：

打通x到根的路径后，我们就获得了一棵以根节点为根的Splay，Splay的中序遍历以根开始，以x结束。这表示根节点是这条链中所有点的祖先，x是这条链中所有点的后代。

然后我们将整棵Splay翻转，Splay的中序遍历变为以x开始，以原来的根节点结束。这表示x是这条链中所有点的祖先，原来的根节点是所有点的后代。

这样，x就变成了原树的根节点了。

整棵Splay翻转时我们先把x节点转到Splay的根，然后push\_rev(x)。

如果语言解释不能使您明白的话，那就上图！

我们将10变为原树的根节点。

首先access(10)。

然后splay(10)。

然后push\_rev(10)。

（在程序实际运行时，Splay只是把7换到了10的右边，并给10打上了rev标记。在图中为了清楚，我直接将标记下传到底部。）

这样就完成了原树的换根。

代码：

void makeroot(int x){
    access(x);
    splay(x);
    push_rev(x);
}

\textbf{findroot(x)}

作用：找到x节点所在原树的根并将根旋转到它所在Splay的根。

实现：

首先打通x到根的路径，然后找到Splay中中序遍历最靠前的点。

从x开始找中序遍历最靠前的点只需把x转到Splay的根，然后一直找它的左儿子就可以了。

找左儿子时别忘了下传标记！

找完记得把原树的根转到Splay的根,删去的话复杂度将不保证！

代码：

int findroot(int x){
    access(x);
    splay(x);
    while(tr[x].s[0]) push_down(x),x=tr[x].s[0];
    splay(x);
    return x;
}

\textbf{split(x,y)}

作用：打通一条从x到y的路径，路径对应的Splay的根为x

实现：

把x变为原树的根，再打通y到根的路径。

注：如果x与y不在同一棵原树中，这个操作不会创造出一条从x到y路径，而是相当于把x变为x所在原树的根，然后打通y到y所在原树的根的路径。

代码：

void split(int x,int y){
    makeroot(x);
    access(y);
    splay(x);//这里也可以写splay(y)，这样Splay的根为y
}

\textbf{link(x,y)}

作用：加一条连接x与y的虚边，使x所在的原树与y所在的原树联通。加边后联通后原树的根节点为y。

实现：

先把x变为x所在原树的根，然后让x的父亲为y（根据认父不认子，加的这条边为虚边）。

如果题目不保证x和y不连通的话，再加一条边就会变成图，而在绝绝绝大多数情况下LCT只能维护树。所以，在这种情况下我们还要进行以下判断后再加边：

将x变为x所在原树的根后，判断y的根是否是x，若是则联通，若不是则不连通。

代码：

void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)//进行连通性判断
        tr[x].p=y;
}

\textbf{cut(x,y)}

作用：断掉直接连接x与y的边（包括虚边和实边），使这棵原树分裂成两棵树。

实现：

打通x与y之间的路径并使根节点为x。如果x与y之间有直接连边的话，这棵Splay只会有两个节点。我们把x的右儿子以及y的父亲都改为0（x没有了右儿子因此右儿子为0，y变成了新原树的根，父亲应为0）。

如果题目不保证x和y之间有直接连边，那我们没法断（没有边怎么断啊）。所以这种情况我们需要特判一下：

动态树的实战应用

1.链上修改查询

这类问题是使用LCT解决的最常见、最模板的问题。进行链上修改和链上查询。如果树的形态不改变，树链剖分一般是更为正统的解法（并且通常跑得比大常数的LCT快）。如果树的形态发生变化或对森林进行维护，那LCT自然更胜一筹。

下面是例题：

P3690 【模板】动态树（Link Cut Tree）