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

前置知识

平衡树 $\text{Splay}​$：博客文章详见「算法笔记」Splay 维护二叉查找树

链剖分

重链剖分

我们所谓的树剖，就是重链剖分的常用称呼。对于每个点，我们选择其最大的子树，将这条连边划分为重边，连向其余子树的边化为分轻边。

长链剖分

对每个点选择其深度最大的儿子作为重儿子，连边即为重边，其余作为轻儿子，连边即为轻边。由此得到了若干条互不相交的长链。

实链剖分

同样将某一个儿子的连边为实边，其余儿子的连边为虚边。只不过虚实是可以动态变化的，因此我们需要用更高级、更灵活的数据结构 $\text{Splay}$ 来维护每一条实链。

基于性质更加优秀的实链剖分，$\text{LCT}$（动态树，即 $\text{Link-Cut Tree}$）应运而生。

性质

  1. 每一个 $\text{Splay}$ 维护的是一条从上到下在原树中深度严格递增的链，且中序遍历 $\text{Splay}$ 得到的点的深度严格递增。
  2. 每个节点包含且仅包含在一个 $\text{Splay}$ 中。

  3. 边分为且仅分为实边和虚边，所有实边包含在 $\text{Splay}$ 中，而虚边总是由一棵 $\text{Splay}$ 指向另一个节点（指向该 $\text{Splay}​$ 中序遍历最靠前的节点在原树中的父亲）。

    为了保持树的形态，我们要让它到其他儿子的边变为虚边，由对应儿子所属的 $\text{Splay}​$ 的根节点的父亲指向该点，而该点不能直接访问该儿子（认父不认子）。

操作

我们首先认识一下 $\text{LCT}$ 支持的操作类型：

  • 查询、修改链上的信息。
  • 对某一个树进行换根操作。
  • 动态连边、删边。
  • 动态维护连通性。
  • 其他神奇的操作。

access(x)

功能：将根节点到 $x$ 上的边都变为实边。

假如我们有一棵树，实边和虚边一开始是这样划分的（图片引用于 YangZhe 的论文 和 FlashHu 的博客）：

那么构成的 $\text{LCT}$ 可能长成这样（绿框中为一个 $\text{Splay}​$，形态不唯一，但是只要满足中序遍历按照深度递增，对结果就没有影响）：

现在我们要执行 $\text{access}(N)$ 操作，把 $A\sim N$ 路径上的边都变成实边，形成一个 $\text{Splay}$。由于性质 $2$，那么肯定有些实边要变为虚边。我们可以得到这样的重新划分：

那么如何实现 $\text{access}(N)$ 的操作呢？

我们从 $N$ 这个点一步步往上进行操作。首先把 $N$ 进行 $\text{splay}$ 操作，使得它变成这个 $\text{Splay}​$ 中的根节点。

为了满足性质 $2​$，那么 $(N,O)​$ 这条边需要从实边变为虚边。由于 $O​$ 的深度比 $N​$ 大，在 $\text{Splay}​$ 中的表现形式就是 $O​$ 在 $N​$ 的右子树中，那么直接把 $N​$ 的右儿子变为空（认父不认子）。得到如图形式：

接着我们把 $N$ 所属的 $\text{Splay}$ 的虚边指向的 $I$（在原树上 $I$ 是 $L$ 的父亲）也转到所属的 $\text{Splay}$ 的根节点，那么边 $(I,K)$ 边需要变为虚边，同时去掉右儿子。这时候把 $(I,N)​$ 变成实边即可。

接下来同理进行一系列操作：

由于 $I$ 所属 $\text{Splay}$ 指向 $H$，故 $\text{splay(H)}$，将 $H$ 的右儿子变为 $I​$。

由于 $H$ 所属 $\text{Splay}$ 指向 $A$，故 $\text{splay(A)}$，将 $A$ 的右儿子变为 $H$。

至此，$A\sim N$ 的路径上的边都变成实边了，而总结整个过程，我们发现只有如下 $4$ 步：

  1. 将节点转到所属 $\text{Splay}$ 的根。
  2. 将其右儿子删除，变为删一个 $\text{Splay}​$ 的根节点。
  3. 更新节点信息。
  4. 将当前点变为虚边所指的父亲，转到步骤 $1$。

代码

void access(Node *x) {
    for (Node *y = null; x != null; x = (y = x)->fa) {
        splay(x), x->ch[1] = y, x->pushup();
    }
}

makeroot(x)

功能：将 $x​$ 成为原树的根节点。

我们首先进行 $\text{access}(x)$ 操作，这样一来我们得到了一条从根节点到 $x$ 的链，$x$ 一定是这个 $\text{Splay}$ 中深度最大的点。根据性质 $1$，在这个 $\text{Splay}$ 中 $x$ 一定没有右子树（没有比 $x$ 深度更大的点）。我们直接翻转整个 $\text{Splay}$，使得所有点的深度都倒过来，$x$ 就没有了左子树，成为了深度最小的点，也就成为了根节点。注意要给这个 $\text{Splay}​$ 打上翻转懒标记。

代码

void makeroot(Node *x) {
    access(x), splay(x), x->reverse();
}

findroot(x)

功能：找到 $x$ 所在的树的根，主要用来判断两点之间的连通性。

我们利用这样一个性质：一棵树的根节点一定是深度最小的点。那么我们先用 $\text{access}(x)$ 把 $x$ 先和根连成一条链，然后用 $\text{splay}(x)$ 将 $x$ 旋转到 $\text{Splay}$ 的根节点。之后根节点一定是 $x​$ 不断往左走得到的（越往左深度越小）。注意在往左走的过程中一定要下传标记！

代码

Node *findroot(Node *x) {
    access(x), splay(x);
    x->pushdown();
    while (x->ch[0] != null) {
        (x = x->ch[0])->pushdown();
    }
    return x;
}

split(x, y)

功能：得到 $x$ 到 $y$ 的一条路径，其中 $y$ 是为路径所在 $\text{Splay}$ 的根节点。

我们可以通过上面的函数直接写出 $\text{split}$ 函数。先把 $x$ 作为根节点，然后得到根节点到 $y$ 的链，将 $y$ 旋转到 $\text{Splay}$ 的根即可。

代码

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

link(x, y)

功能：连一条虚边 $(x, y)$（如果已经连通则不操作）。

我们将 $x$ 变成原树的根，然后将 $x$ 的父节点直接设为 $y$ 即可。因为在 $\text{findroot}(y)$ 中已经执行了 $\text{access}(y)$ 和 $\text{splay}(y)$，则 $y$ 成为了所在 $\text{Splay}​$ 的根节点。

连通性的检查：$x$ 成为根节点后，如果 $\text{findroot}(y)=x$ 则说明 $x, y$ 连通。

代码

void link(Node *x, Node *y) {
    makeroot(x);
    if (findroot(y) != x) x->fa = y;
}

cut(x, y)

功能：切断边 $(x, y)$（如果没有边则不进行操作）

首先我们把 $x$ 变成根节点，如果存在边 $(x, y)$，那么 $x$ 的深度一定比 $y$ 浅，则 $x$ 是 $y$ 的左儿子，$y$ 是 $x​$ 的父节点。

但是如果不保证操作合法呢？我们需要很多条件来判断 $(x, y)$ 这条边是不存在的。不存在边 $(x, y)​$ 的条件（满足一者即可）：

  1. 如果 $x,y$ 不在同一棵树内，那么不存在边。
  2. 如果 $x$ 的父亲不是 $y$，则意味着 $x,y$ 虽然在同一个 $\text{Splay}$ 中却没有连边。
  3. 如果 $x$ 的右子树非空，那么意味着以 $y$ 为根的中序遍历中 $x$ 和 $y​$ 不相邻，则没有边相连。

代码

void cut(Node *x, Node *y) {
    makeroot(x);
    if (findroot(y) == x && x->fa == y && x->ch[1] == null) {
        x->fa = y->ch[0] = null, y->pushup();
    }
}

区别

rotate(x)

功能：将 $x​$ 向上旋转。

和普通 $\text{Splay}​$ 不同的是，我们在修改 $x​$ 的祖父的儿子时，必须判断 $x​$ 的父亲是否为所在 $\text{Splay}​$ 的根。因为如果不判断的话，$0​$ 的儿子就会被定义为 $x​$，而 $x​$ 则永远不可能成为根节点，在 $\text{splay}​$ 函数中将会无限循环。

代码

void rotate(Node *x) {
    Node *y = x->fa, *z = y->fa;
    int k = x->get();
    !y->isroot() && (z->ch[y->get()] = x), x->fa = z;
    y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
    x->ch[!k] = y, y->fa = x;
    y->pushup();
}

splay(x)

功能：将 $x​$ 旋转到 $\text{Splay}​$ 的根节点。

由于 $\text{LCT}$ 中对 $\text{Splay}$ 有翻转操作，那么我们在 $\text{splay}(x)$ 之前，必须将 $x$ 的所有祖先的标记下放，我们用递归访问所有的祖先并下放标记。

代码

void splay(Node *x) {
    pushtag(x);
    while (!x->isroot()) {
        Node *y = x->fa;
        if (!y->isroot()) {
            rotate(x->get() == y->get() ? y : x);
        }
        rotate(x);
    }
    x->pushup();
}

代码

以「Luogu 3690」Link Cut Tree 为例。

#include <cstdio>
#include <algorithm>

const int N = 3e5 + 5;

int n, m;

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int val, sum;
    bool rev;
    Node() {
        ch[0] = ch[1] = fa = null;
        val = sum = rev = 0;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void reverse() {
        rev ^= 1, std::swap(ch[0], ch[1]);
    }
    void pushup() {
        sum = ch[0]->sum ^ ch[1]->sum ^ val;
    }
    void pushdown() {
        if (rev) {
            ch[0]->reverse();
            ch[1]->reverse();
            rev = 0;
        }
    }
} *a[N];

struct LCT {
    LCT() {
        null = new Node();
        null->ch[0] = null->ch[1] = null->fa = null;
    }
    void build(int n) {
        for (int i = 1; i <= n; i++) {
            a[i] = new Node();
        }
    }
    void clear(int n) {
        delete null;
        for (int i = 1; i <= n; i++) {
            delete a[i];
        }
    }
    void pushtag(Node *x) {
        if (!x->isroot()) pushtag(x->fa);
        x->pushdown();
    }
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int k = x->get();
        !y->isroot() && (z->ch[y->get()] = x), x->fa = z;
        y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
        x->ch[!k] = y, y->fa = x;
        y->pushup();
    }
    void splay(Node *x) {
        pushtag(x);
        while (!x->isroot()) {
            Node *y = x->fa;
            if (!y->isroot()) {
                rotate(x->get() == y->get() ? y : x);
            }
            rotate(x);
        }
        x->pushup();
    }
    void access(Node *x) {
        for (Node *y = null; x != null; x = (y = x)->fa) {
            splay(x), x->ch[1] = y, x->pushup();
        }
    }
    void makeroot(Node *x) {
        access(x), splay(x), x->reverse();
    }
    Node *findroot(Node *x) {
        access(x), splay(x);
        x->pushdown();
        while (x->ch[0] != null) {
            (x = x->ch[0])->pushdown();
        }
        return x;
    }
    void split(Node *x, Node *y) {
        makeroot(x), access(y), splay(y);
    }
    void link(Node *x, Node *y) {
        makeroot(x);
        if (findroot(y) != x) x->fa = y;
    }
    void cut(Node *x, Node *y) {
        makeroot(x);
        if (findroot(y) == x && x->fa == y && x->ch[1] == null) {
            x->fa = y->ch[0] = null, y->pushup();
        }
    }
};

int main() {
    scanf("%d%d", &n, &m);
    LCT T;
    T.build(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]->val);
    }
    for (int i = 1; i <= m; i++) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) T.split(a[x], a[y]), printf("%d\n", a[y]->sum);
        if (opt == 1) T.link(a[x], a[y]);
        if (opt == 2) T.cut(a[x], a[y]);
        if (opt == 3) T.splay(a[x]), a[x]->val = y;
    }
    T.clear(n);
    return 0;
}

习题

本文题单摘录自 FlashHu 的博客

维护链信息

维护连通性

维护边权

维护子树信息

维护树上染色连通块

特殊题型

最后修改：2019 年 09 月 25 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏