Link-Cut Tree

This_Rrhar · 2024-05-20 19:19:49 · 算法·理论

前置知识：文艺平衡树、树剖（非必要）。

简介

动态树问题

动态树问题，指的是维护一个森林，支持加边、断边，保证之后仍是森林，维护该森林的一些信息。

先看例题：

给 n 个点，点有点权。m 次操作：

这是树剖模板题。

再加两个操作：

这就变成了动态树问题。

回顾树剖

给每个点重新标记 DFS 序，重儿子在前，此时一条链上的重儿子组成重链，在 DFS 序中连续。

再把每个轻儿子都视为一条重链，容易证明一棵树的重链数为 O(\log n)，可以用线段树维护。

引入实链剖分

树剖不能解决动态树问题的原因是：重链可能会因断边而变更，且维护这种变更的开销过大。

所以我们希望对于每个点，都能够随时变更剖分的边。

我们把当前被剖分的边叫做实边，其余的边叫做虚边，与这两种边对应的点是实儿子和虚儿子。与树剖类似，多条连续实边称为实链，多条连续虚边成为虚链。

Link-Cut Tree

LCT 使用一些 Splay 来代替线段树，实现 DFS 序上的动态树剖。对于每条实链，建一个 Splay 来维护 DFS 序中对应区间中的信息。

引入辅助树

一棵辅助树由一些 Splay 构成，由于 Splay 维护的是链，所以辅助树维护的是原树的一棵子树。多棵辅助树就构成了 Link-Cut Tree。

如何把多棵 Splay 联系起来？因为每棵 Splay 对应一条实链，所以链顶的父亲属于另一颗 Splay。我们将 Splay 中树根的父亲设为链顶的父亲，这条边实际上就对应了树根与链顶父亲间的虚边。

注意：树根到链顶父亲之间有着儿子认父亲，但父亲不认儿子的关系，因为我们并没有给链顶父亲新增一个儿子。

由于一棵辅助树就是原树中的一棵子树，所以维护辅助树就达到了维护原树的目的。

例如原树形态如下图（real 为实边，imag 为虚边）：

那么辅助树可能是这样的：

需要注意的是辅助树中 Splay 的形态，因为 Splay 维护的链实际上是基于 DFS 序进行维护的。

那么我们可以开始考虑如何在辅助树上完成动态树问题了。

要实现的操作

• notroot(x)：查询 x 是否不是所在 Splay 的根。

• access(x)：把路径 rt\leftrightarrow x 改成一条实链，rt 是 x 所在辅助树的树根。

• makeroot(x)：使 x 成为所在原树的根。

• findroot(x)：查询 x 所在原树的树根。

• split(x)：将路径 x\leftrightarrow y 放到一棵 Splay 中。

• link(x,y)：连边 (x,y)。

• cut(x,y)：断边 (x,y)。

notroot(x)

由于根有儿子认父亲、父亲不认儿子的性质，所以 x 不为根的充要条件为 x 的父亲的左右儿子之一为 x。

bool ntr(ll x){return ls(f[x])==x||rs(f[x])==x;}

rotate(x)

与 Splay 基本相同，但需注意此时 z 可能属于另一棵 Splay，要用 notroot(y) 判断，并且要将该句写在最前面，否则 z 的儿子可能会被改变。

至于为什么不用判断 y 是否属于另一棵 Splay，这是因为在 LCT 中，我们只需要用 splay(x) 将 x 旋转到所在 Splay 的根，所以 rotate(x) 只可能在 x 不为根时才可能执行，故 x,y 必在同一棵 Splay 中。

void rotate(ll x)
{
    ll y=f[x],z=f[y];
    bool d=dir(x);
    if(ntr(y))son[z][dir(y)]=x;
    if(son[x][d^1])f[son[x][d^1]]=y;
    son[y][d]=son[x][d^1];
    son[x][d^1]=y;
    f[y]=x;
    f[x]=z;
    push_up(y),push_up(x);
}

splay(x)

同样与原版 Splay 略有不同：需要把路径 rt\leftrightarrow x 上所有点都下传标记。具体地，将 x\to rt 上的所有点压入栈中，然后依次将栈中所有点进行标记下传。

void splay(ll x)
{
    ll y=x;
    st.push(y);
    while(ntr(y))st.push(y=f[y]);
    while(!st.empty())push_down(st.top()),st.pop();
    while(ntr(x))
    {
        y=f[x];
        if(ntr(y))rotate(dir(x)^dir(y)?x:y);
        rotate(x);
    }
    push_up(x);
}

access(x)

LCT 最核心的操作。

要把虚边 (u,v) 变成实边，只需将 u 的某个儿子修改成 v 即可，u 与之前连的儿子间的实边会自动变成虚边。

我们以 x\to rt 的顺序，每次先把当前点旋转到所在 Splay 的根，这样下一个点一定和当前点不在同一 Splay 中，然后把当前点与上一个点之间的虚边变成实边即可。

void access(ll x){for(int y=0;x;x=f[y=x])splay(x),rs(x)=y,push_up(x);}

makeroot(x)

先把 rt\leftrightarrow x 变为实链，然后把 x 旋转到所在 Splay 的根即可。

这时我们还要保证中序遍历的正确性，容易发现 x 变为根后，DFS 序中从 1 到 x 这一段就翻转了，所以给 x 做一次区间翻转即可。

void makeroot(ll x){access(x),splay(x),push_rev(x);}

findroot(x)

与 makeroot(x) 类似，也是先将 x 变为原树的根，此时根据中序遍历的性质，原树的根可以从 x 一直往左儿子走到头得到，然后把原树的根再 Splay 回来恢复 DFS 序，所以不需要区间翻转。

ll findroot(ll x)
{
    access(x),splay(x);
    while(ls(x))push_down(x),x=ls(x);
    splay(x);
    return x;
}

split(x,y)

容易先让 x 成为根，再把 x\leftrightarrow y 变成实链，如果要让 y 做根则再进行一次 Splay。

void split(ll x,ll y){makeroot(x),access(y),splay(y);}

link(x,y)

首先把 x 变成辅助树的根，然后判断 x,y 是否在同一棵辅助树中，如果不是 x 那么将 x 的父亲设为 y 即可。

void link(ll x,ll y)
{
    makeroot(x);
    if(findroot(y)!=x)f[x]=y;
}

cut(x,y)