发布于 由東風谷早苗（こちやさなえ）

Link/Cut Tree

前置技能：Splay（伸展树）

Link/Cut Tree 是一种维护森林连通性和其他树上问题的思想暴力的数据结构。

它可以干什么呢：

  • 森林中动态连边，切边，换树根
  • 维护森林连通性（并查切集）
  • 所有树链剖分的树上路径操作
  • Splay加持的一些区间恶心操作

暴力换根，暴力连边，暴力切边，暴力Splay，暴力……总而言之就是暴力

——军训时盯着印出来的LCT材料恍然大悟时我的第一句话

在进行操作之前我们需要明确一些概念：

Splay中每个节点最多只能有两个儿子，为了存下许多Splay存不下的边，我们会把一个普通的树存成很多Splay BST和一些由Splay根节点的father指针连接的轻边。
（有人会把重边成为“实边”，把轻边成为“虚边”，因为边的轻重虚实不是像树剖一样按照子树大小固定分配的，而是动态改变着的）

这只是一个粗略的概念，下面开始详细解释：

图中原树中加粗的为重边。观察得出以下性质：
（1）每个Splay代表原树中的一条首尾相连的重链，其中所有节点深度不同且连续，按照BST的规则有序排布；
（2）由于每个节点只有最多两个记录的儿子，轻边只能由子节点向父节点单向连接。
我们规定，轻边通过由节点所在Splay的根节点的father指针指向原树中父亲节点的方式存储，
这条边代表着由这个Splay中深度最小的节点连向原树中其父亲节点的一条轻边。
（这样规定主要是为了方便Access和其他轻重边切换的操作）

结构大致是这样，接下来是各种操作（以下所有BST均左小右大）

Access

针对一个节点处理，使得一颗以根节点为深度最小节点，该节点为深度最大节点的完整的Splay出现。

这是LCT中最为核心的操作之一，循环中操作只有四步：
（1）把当前节点Splay到根节点；
（2）把这个节点的右子直接设置为上一个节点（当前节点是上一个节点子树中深度最小节点的父节点，其深度一定比上一个节点子树中所有节点更小，按照BST的规则，上一个节点应设为右子；之前的右子边自动变成轻边）；
（3）更新当前节点（改了一个儿子，要更新）；
（4）上一个节点设为当前结点，当前结点设为父节点，继续循环直至到达原树根节点（father为null）

void access(node* p) {
    node* prev = nullptr;
    // 上面这一行使得要Access的节点所在Splay中所有深度更大的节点被切离到另一个Splay中
    while (p != nullptr) {
        splay(p);
        p->rson = prev;
        update(p);
        prev = p;
        p = p->father;
    }
}

看完代码，我们考虑一下为什么右子可以直接单方面置成轻边，而左子不可以

Splay是一个二叉搜索树，一个点的右子树包含了Splay里所有深度大于这个点的点，而LCT的Splay又保证了一个Splay中的点深度连续，所以，按照LCT的轻边定义，把右子边单方面置为轻边即代表了原树中这个节点和他的一个子节点——Splay中右子树中深度最小的节点，其深度恰好比这个节点深1——之间的边变成了轻边。

有了Access操作，剩下的操作都变得十分简单暴力。

MakeRoot

任意重新指定原树中的根。

思想十分简单，只有两步：
（1）Access一下，再Splay一下，使得这个节点变成其Splay中深度最大，位置最高的节点。此时这个节点应该没有右子；
（2）直接把这个节点所在子树整个翻转，所有节点的深度都倒过来了，原树树根深度变得最大，这个节点反而成了深度最小的根节点。

void makeroot(node* p) {
    access(p);
    splay(p);
    p->lazy = !p->lazy; //直接打上翻转标记
}

现在有了翻转lazy标签，别忘了下放。

FindRoot

查找一个节点在原树中的根。

思想也很简单，分三步：
（1）Access一下，这时要找的根节点一定和这个节点在同一个Splay中；
（2）Splay一下，这时这个节点在Splay中位置最高，要找的根节点一定在这个节点左侧；
（3）循环一直找当前节点的左子节点，找到Splay树中深度最低的节点即为根节点。（别忘了下放lazy！）

node* findroot(node* p) {
    access(p);
    splay(p);
    pushdown(p); // 这样别扭地pushdown主要是为了确保每一次访问p的左子时结果都是正确的
    while (p->lson != nullptr) {
        p = p->lson;
        pushdown(p);
    }
    return p;
}

接下来的内容几乎没有了思想难度。

Link

连接两个节点。

直接MakeRoot一个节点再把他的father（现在一定是null）设为另一个节点就好啦

void link(node* x, node* y) {
    makeroot(x);
    if (findroot(y) != x) // 随便FindRoot，不在同一颗树里y怎么折腾都不会影响x
        x->father = y;
}

Cut

将两个的相连的点之间的边切开。

如果保证切边合法倒是很简单，直接MakeRoot(x); Access(y); Splay(y);然后把y的左子和x的father置为null就切开了

void cut(node* x, node* y) {
    makeroot(x);
    access(y);
    splay(y);
    y->lson = x->father = nullptr;
    update(y);
}

如果不保证合法呢？考虑以上三步完成后，xy两个点在同一个Splay中深度连续，x深度小于y，y在x上方的情形：
（1）x一定是y的左子
（2）x一定没有右子（没有深度小于y大于x的点）

于是我们就可以写出以下的代码啦

void cut(node* x, node* y) {
    makeroot(x);
    // FindRoot内置Access和Splay
    if (findroot(y) != x || y->lson != x || x->rson != nullptr)
        return;
    y->lson = x->father = nullptr;
    update(y);
}

切完边别忘了更新上面的节点！

Split

把一个以一个点起始，另一个点结束的Splay分离出来。

其实有很多人不把这个东西单独算作一个操作的，因为他很简单：

nod（e* split(node* x, node* y) {
    makeroot(x);
    access(y);
    splay(y);
    return y;
}

然后就结束啦

时间复杂度：均摊 \(O(\log_2 n)\)，常数不可思议地大
（似乎是Splay玄学的势能分析对于整棵LCT依然成立而保持了这个理论复杂度，可以把整个LCT看成一个大Splay？）

模板：洛谷P3690 【模板】Link Cut Tree （动态树），评测R10627118

代码里还有很多和Splay不同的细节，主要就是判断节点不是Splay的根节点的NotRoot、Rotate的时候特判节点是不是Splay的根以及Splay操作时一直把节点旋转到所在Splay的根节点位置这三点，记得要注意

/*
 DOCUMENT NAME "20180909-luogu3690.cpp"
 CREATION DATE 2018-09-09
 SIGNATURE CODE_20180909_LUOGU3690
 COMMENT P3690 【模板】Link Cut Tree（动态树）
*/

#include <cstdlib>
#include <iostream>
using namespace std;

constexpr int MaxN = 7e5 + 10, MaxM = 7e5 + 10;

template<typename IntType = int>
IntType read() {
    IntType ans = 0;
    int c;
    while (!isdigit(c = getchar()));
    do { ans = (ans << 1) + (ans << 3) + c - '0'; } while (isdigit(c = getchar()));
    ungetc(c, stdin);
    return ans;
}
template<typename IntType>
void read(IntType& x) { x = read<IntType>(); }
template<typename IntType, typename... Args>
void read(IntType& x, Args&... args) { x = read<IntType>(); read(args...); }

int n, m;

struct node {
    node* lson, *rson;
    node* father;
    int val, xorsum;
    bool lazy;
};

node* nodes[MaxN];
node mem[MaxN], *memtop = mem;
#define ALLOCATE (++memtop)

typedef int sontype;
constexpr sontype lson = 0, rson = 1, lightson = 2;
constexpr sontype tellwhich(node* son) {
    if (son->father == nullptr)
        return lightson;
    else if (son->father->lson == son)
        return lson;
    else if (son->father->rson == son)
        return rson;
    else
        return lightson;
}
node*& getson(node* father, sontype type) { return type == lson ? father->lson : father->rson; }
void connect(node* father, node* son, sontype type) {
    if (father != nullptr)
        getson(father, type) = son;
    if (son != nullptr)
        son->father = father;
}

bool notroot(node* p) { return p->father != nullptr && (p->father->lson == p || p->father->rson == p); }

void update(node* p) {
    p->xorsum = p->val;
    if (p->lson != nullptr)
        p->xorsum ^= p->lson->xorsum;
    if (p->rson != nullptr)
        p->xorsum ^= p->rson->xorsum;
}

void rotate(node* p) {
    sontype t = tellwhich(p);
    node* f = p->father, *b = getson(p, 1 - t);
    if (notroot(f))
        connect(f->father, p, tellwhich(f));
    else
        p->father = f->father;
    connect(p, f, 1 - t);
    connect(f, b, t);
    update(f);
    update(p);
}

void pushdown(node* p) {
    if (p->lazy) {
        swap(p->lson, p->rson);
        if (p->lson != nullptr)
            p->lson->lazy = !p->lson->lazy;
        if (p->rson != nullptr)
            p->rson->lazy = !p->rson->lazy;
        p->lazy = false;
    }
}

void pushchain(node* p) {
    if (notroot(p))
        pushchain(p->father);
    pushdown(p);
}

void splay(node* p) {
    pushchain(p);
    while (notroot(p)) {
        if (notroot(p->father))
            if (tellwhich(p) == tellwhich(p->father))
                rotate(p->father);
            else
                rotate(p);
        rotate(p);
    }
}

void access(node* p) {
    node* prev = nullptr;
    while (p != nullptr) {
        splay(p);
        p->rson = prev;
        update(p);
        prev = p;
        p = p->father;
    }
}

void makeroot(node* p) {
    access(p);
    splay(p);
    p->lazy = !p->lazy;
}

node* findroot(node* p) {
    access(p);
    splay(p);
    pushdown(p);
    while (p->lson != nullptr) {
        p = p->lson;
        pushdown(p);
    }
    return p;
}

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

void cut(node* x, node* y) {
    makeroot(x);
    if (findroot(y) != x || y->lson != x || x->rson != nullptr)
        return;
    y->lson = x->father = nullptr;
}

node* split(node* x, node* y) {
    makeroot(x);
    access(y);
    splay(y);
    return y;
}

void changepnt(node* p, int val) {
    access(p);
    splay(p);
    p->val = val;
    update(p);
}

int k, x, y;

int main(int argc, char* argv[]) {

    read(n, m);
    for (int i = 1; i <= n; i++) {
        node* p = nodes[i] = ALLOCATE;
        p->val = p->xorsum = read();
    }
    for (int i = 1; i <= m; i++) {
        read(k, x, y);
        if (k == 0)
            printf("%d\n", split(nodes[x], nodes[y])->xorsum);
        else if (k == 1)
            link(nodes[x], nodes[y]);
        else if (k == 2)
            cut(nodes[x], nodes[y]);
        else if (k == 3)
            changepnt(nodes[x], y);
    }

    return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注