0017: 动态树LCT简述

FugiPig · 2024-07-21 19:51:22 · 算法·理论

0017: 动态树LCT简述

1. 简介

1.1 一些定义与 LCT 辅助树

动态树问题: 维护一个森林, 支持加入或删除一些边, 维护一些信息. LCT(Link Cut Tree), 就是一种常用的动态树.

回顾树链剖分, 我们将一棵树剖分成若干重链, 用线段树等数据结构维护重链上的信息. 而在 LCT 中, 由于我们在连边时需要使某个点成为根, 所以选用 Splay 实现的文艺平衡树.

由于我们需要合并一些链, 根据子树大小划分的重链不再适用, 而是使用实链. 在 LCT 的原树(如上图)上, 每个非叶节点有一个实儿子(父亲认的), 连接实儿子的边叫实边(上图中实线), 还有若干个虚儿子(父亲不认的), 连接的叫虚边(虚线). 若干条实边连起来, 构成一条实链, 我们用 Splay 维护. Splay 的中序遍历对应这条实链从上到下, Splay 的根的父亲是该实链顶端(显然是个虚儿子)的父亲. 由此, 多棵 Splay 构成了一棵辅助树, 如下图:

1.2 变量声明

接下来 Splay 节点定义的一般变量如下:

• ch[N][2]节点的两个儿子.
• fa[N]节点的父亲.
• rev[N]翻转标记(文艺平衡树).

与维护权值有关的变量(以维护路径和为例, 下列代码中不给出与此有关的部分):

• val[N]点权
• sum[N]路径和(所在 Splay 的一个子树)
• siz[N]Splay 中子树大小
• col[N]权值标记
• ...

还有一些宏定义:

• #define ls ch[x][0]
• #define rs ch[x][1]

2. 函数声明

2.1 对树形态无改变的操作

isrt(x)

判断该点是否为所在 Splay 的根.

bool isrt(int x)
{
    return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}

get(x)

判断该点是父亲的哪个儿子.

int get(int x)
{
    return ch[fa[x]][1]==x;
}

reverse(x)

打区间翻转标记.

void reverse(int x)
{
    rev[x]^=1;
    swap(ls,rs);
}

pushup(x)

上推标记.

void pushup(int x)
{
    siz[x]=siz[ls]+siz[rs]+1;
}

pushdown(x)

下传标记.

void pushdown(int x)
{
    if(rev[x])
    {
        reverse(ls);
        reverse(rs);
        rev[x]=0;
    }
}

update(x)

对该点到所在 Splay 的根的路径上的点从上到下下传标记.

void update(int x)
{
    if(!isrt(x))update(fa[x]);
    pushdown(x);
}

2.2 Splay 原有的操作

rotate(x)

将该点向上旋转一层.

void rotate(int x)
{
    int y=fa[x],z=fa[y],p=get(x);
    if(!isrt(y))ch[z][get(y)]=x;
    ch[y][p]=ch[x][!p];
    fa[ch[x][!p]]=y;
    ch[x][!p]=y;
    fa[y]=x;
    fa[x]=z;
    pushup(y);
    pushup(x);
}

splay(x)

将该点旋转到所在 Splay 的根.

void splay(int x)
{
    update(x);
    for(int f=fa[x];!isrt(x);rotate(x),f=fa[x])
        if(!isrt(f))rotate(get(x)==get(f)?f:x);
}

2.3 新操作

access(x)

构造一条以原树的根开始, 以 x 结束的链.

设 p 为当前已构造出的链构成的 Splay 的根, 初始时为 0. 我们要将 x 和 p 各自所在的链合并, 只需将 x Splay 到根, 将 p 作为 x 的右儿子, x 原来的右儿子就成为了 x 的一个虚儿子. 此时, 以 x 为根的 Splay 表示了我们已构成的链, 因此 p\leftarrow x, x\leftarrow fa_x. 如此循环往复, 直到 p 成为原树的根.

int access(int x)
{
    int p;
    for(p=0;x;p=x,x=fa[x])
    {
        splay(x);
        rs=p;
        pushup(x);
    }
    return p;
}

这里的 access 操作还有一个返回值, 即最后一次合并时的 x, 它有两个含义:

• 连续两次 access 操作时, 第二次的返回值表示这两个点的 LCA(当然要在同一棵树上).
• 表示我们构造的链的 Splay 的根, 因为最后我们对其进行了 splay 操作.

makeroot(x)

使 x 成为原树的根.

我们将原树看做一个由父亲向儿子连边的 DAG, 可以发现, 只需要翻转 x 到根的路径上的边即可使 x 成为新的根.

void makeroot(int x)
{
    x=access(x);
    reverse(x);
}

find(x)

寻找 x 所在原树的根.