<算法>Link/Cut Tree(动态树)

注意了,LCT\not=动态树
当然没啥

建议这篇文章看两遍以后再去看看其他文章,反过来也OK,因为码风太毒瘤了...
当然指针的写法用来理解思想是很棒的

前言

树链剖分用的是重链剖分,我们把一棵树搞成了一条链,然后用一个像线段树这样的数据结构去维护她。
但是线段树不够灵活,我们没法对树的形态进行变化,于是Daniel Dominic SleatorRobert Endre Tarjan(好眼熟)发明了这个东西。这个东西使用的是实链剖分,也就是把所有的边随心划分为实边和虚边,连续的不可延伸的一条链即为一条实链。为了方便查看性质,我把性质分为了一些小点,可能比较乱:(我们指的实链是极大的,即不可再延伸)

  • 所有的点都包含且仅包含在一条实链中;(也就是一个点也可以成为一条实链)
  • 一条实链不包含深度相同的点;(当然了,点的深度是连续变化的,不要问为什么,问就是不知道)
  • 我们用一棵Splay树维护一条实链,所以我们维护了一片Splay森林;
  • 一棵Splay树的中序遍历代表了这棵Splay树维护的原树的实链从浅到深的点编号;
  • 一棵Splay树的根节点可能也有父亲,指向这棵Splay维护的实链的最浅的节点在原树的父亲(也就是Splay中序遍历的第一个点在原树中的父亲),与其他的Splay边不同的是,这个点的父亲的两个子节点均不是这个点(虚边认父不认子)
  • 除此以外Splay的形态与原树再无关系(如有错误请指出)

Splay树是一棵BST,所以我们任意进行旋转操作,而保证我们维护的原树信息不被破坏(即旋转不破坏中序遍历)

那我们来学习一下LCT的窒息操作吧:

LCT操作

我们先来认识一下我们的一个节点:

struct Node
{
    Node *fa, *c[2];
    int v, s;//v:点权 s:子树和自己的xor和
    bool t;//翻转标记
};

这是伪代码所以用了指针

我们要知道每个点的父亲和两个儿子,然后make_root有个翻转标记,其他就自己看情况了。为了写洛谷的板子,我加了三个东西,见注释

update、pushdown、rotate、splay

这是基本函数了
update别名pushup

个人比较喜欢把reverse提出来写,不容易错。
你会发现很多人是下放标记的时候才更新自己这个节点的,但是我喜欢用线段树的方式维护标记。

inline void update(void)
{
    s = v ^ (c[0] ? c[0]->s : 0) ^ (c[1] ? c[1]->s : 0);
    //只是这道题的update
}

inline void reverse(void)
{
    t ^= 1;
    swap(c[0], c[1]);
}

inline void pushdown(void)
{
    if (t)
    {
        t ^= 1;
        if (c[0])
            c[0]->reverse();
        if (c[1])
            c[1]->reverse();
    }
}

然后是与莆通的Splay不一样的rotate和splay了。先看rotate:

inline bool not_root(void) { return fa && (fa->c[0] == this || fa->c[1] == this); }
inline void rotate()
{
    Node *ffa = fa->fa;
    bool ty = which();
    if (fa->not_root())//这里!!
        ffa->c[fa->which()] = this;
    fa->c[ty] = c[!ty];
    if (fa->c[ty])
        fa->c[ty]->fa = fa;
    fa->update();
    c[!ty] = fa;
    fa->fa = this;
    fa = ffa;//一棵Splay树的根节点的父亲指向这棵Splay维护的实链的最浅的节点
             //在**原树**的父亲(也就是Splay中序遍历的第一个点在**原树**中的父亲)
    update();
}

你发现我在这个代码块里面写了两个函数。第一个函数判断一个点是否为Splay的根,判断方法在前言提到过了,rotate不一样的地方就在于判断是否有爷爷(爸爸的爸爸)那里,其他都一样。记得update。

然后是Splay了,不一样的地方在于我们在Splay这个点之前先确保她到父节点的路径畅通无阻(标记全部下放)再转:

inline void down(void)
{
    stack<Node*> st;
    st.push(this);
    for (Node *i = this; i->not_root(); i = i->fa)
        st.push(i->fa);//这样保证Splay根能进入栈
    do
        st.top()->pushdown();
    while (st.pop(), st.empty() == false);
}
inline void splay(void)
{
    down();
    while (not_root())
    {
        if (fa->not_root())//记得用新方式
            ((fa->which() == which()) ? fa : this)->rotate();
        rotate(); //双旋啊喂
    }
}

access

(下面的东西会很严格地区分Splay树和原树,我学的时候就是在这方面理解了很久。设计哪种树的会加粗显示)

access:打通原树根节点到指定点的路径(并且指定点下面不再链接实边)

  1. 将当前点Splay到根以确保其父亲指向其实是虚边
  2. 将当前点的右儿子换成之前的Splay根
  3. 你改变了儿子,记得更新...
  4. 麻烦你的父亲认你

解释一下x->c[0] = p:

  1. 当你是最开始的点的时候,p=0,相当于切断了与原树更深的点的联系,这时你所在的Splay树维护的实链中,你就是中序遍历最后面一个点;
  2. x=x->fa的时候已经记录了你,这时候你的原树父亲也Splay了,并且也让自己成为了她在的实链的最深点,然而她还是你的原树父亲,你们两个人之间只相隔一条虚边,这时你的爸爸认了你,OK你们之间的边就是实边了;
  3. 但是你良心发现,爸爸原来认的那个右儿子直接被砍了!你很担心父亲原来认的右儿子,因为那个儿子和你的爸爸之间变成了虚边,而按照定义,这条虚边必须从/一个Splay的根/链接到/Splay对应的实链最浅点/在原树的父亲,于是你就问老猫你自己,这条被“降级的”边有这个性质吗?
    (再次强调,一棵Splay维护一条从浅到深的实链)
    于是老猫告诉你你告诉你自己,想一想更改儿子前这个Splay的中序遍历,然后想一想删除(而不是替换)这条实边以后原来的Splay的中序遍历和新的Splay的中序遍历。这个我倒是可以画个很简单的图:

注意我们只是让爸爸不认儿子了,儿子还是认爸爸的

好了,splay没问题了,替换儿子也没问题了,我相信聪明的你一定可以理解update。

Node *access(Node *ch = 0)
{
    Node *p = 0;//记录上一棵Splay树的根,因为要打成实链,就让当前点认儿子就好了
    //再次强调,一棵Splay树只维护从上到下的一条链,所以任意旋转都不会破坏其对于的原树信息
    for (Node *x = this; x; p = x, x = x->fa)
    {
        x->splay();
        x->c[1] = p;
        x->update();
    }
    return p;
}

好吧对着代码再说一下,p是上一条实链的Splay的根,我们要让两条实链链接在一起,就要让p所在实链的最浅点的父亲认我们Splay的根为右儿子(右儿子代表着p所在的Splay的所有节点均在这个父亲在原树的重链位置的下方且这个父亲在原树的重链的下方的点只有p所在Splay的点)。

当然这个板子还返回了一个Node指针,这个指针表示原树的根所在的 Splay的根。并且据OI Wiki,连续两次 Access 操作时,第二次 Access 操作的返回值等于这两个节点的 LCA.

make_root

让其成为原树的根,原树的根,原树的根。
原树原树原树

啊啊啊,经过了access的洗礼以后,后面对你来说都是小kcase了

inline void make_root() { access()->reverse(); }

喂,你觉得简单也要解释啊!
好好好介绍一下。我们先确保我们要make_root的这个点在当前原树的根所在的Splay,然后我们把这个Splay整个翻转过来...
蛤?整个翻转过来?
啊啊啊的确有点难理解呢。首先我们再次重复:一棵Splay维护一条从浅到深的实链,然后你想象一下你access以后,太子在这条实链的最下面,在树的很深的地方。然后你抓住太子,把这棵树提了起来,想象一下这棵树像一串有好多分叉的钥匙串,由于重力作用,你提着的那个太子就是根了。我们再看看她所在的实链,发现浅的点变深,深的点变浅,所以说翻转了Splay相当于翻转了中序遍历,自然就让这条链变成了太子为最浅点。再看看其他的Splay,没有影响,因为她们和这个太子所在的链只有虚链父子关系。

哦对了,我们只保证了这个点现在在原树的根了,并没有保证是Splay的根...这和其他模板是不一样的。其他模板是酱的:

inline void make_root()
{
    access();
    splay();
    reverse();
}

这样还保证了这个点是Splay的根。所以下面的代码和其他板子可能会不同。

find_root

寻找一个点所在的Splay对应在原树的树根。因为我们其实维护了一片原树森林来着...
最大的用处就是判断两个点在不在一棵原树
如果你做的题没有删边操作请用并查集...
先access保证在原树根所在的Splay,然后转到Splay根上,最后一直往左走,得到中序遍历最小的点

inline Node *find_root()
{
    access();
    splay();
    Node *r = this;
    while (r->c[0])
        r = r->c[0];
    return r;
}

其实我想(只是想)不splay也行,一直跳到Splay根,然后在往左走。但是我想find_root之后的操作一般都是连边、删边,需要两个点在Splay的根

split

原树上拉出一条x-y的实链。我定义this为Splay的根,bottom是树的根:

inline void split_to(Node *bottom)
{
    bottom->make_root();
    access();
    splay();
}

不读代码了

link

把一个点在原森林连到to上

inline void link_to(Node *to)
{
    make_root();
    if (to->find_root() == this)
        return;
    splay();//这里和其他模板可能不太一样
            //是因为我们的make_root不保证当前点在Splay根
    fa = to;
}

相当于是新建了一条虚边

cut

切断一条原树的边

inline void cut(Node *another)
{
    another->make_root();
    if (find_root() !=another)
        return;
    if (c[0] == 0 || another->fa != this)
        return;
    //assert(another->c[0] == 0 && another->c[1] == 0);
    //这句话亲测不会assert fail
    c[0] = another->fa = 0;
    update();
}

先把一个点变成当前原树的树根,然后把自己这个点变为Splay的根。如果这两个点在原树相连的话因为中序遍历的关系,树肯定是长这个亚子的(A是another,B是this

  B
 / \
A   ...

(大家都不想看的)代码

跑得比数组实现快并不
比大多数数组实现快

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cassert>

struct Read
{
    //...
} read;

using std::min;
using std::swap;

const int N = 100000 + 10;

struct Node
{
    Node *fa, *c[2];
    int v, s;
    bool t;
    inline void update(void) { s = v ^ (c[0] ? c[0]->s : 0) ^ (c[1] ? c[1]->s : 0); }
    inline void reverse(void)
    {
        t ^= 1;
        swap(c[0], c[1]);
    }
    inline void pushdown(void)
    {
        if (t)
        {
            t ^= 1;
            if (c[0])
                c[0]->reverse();
            if (c[1])
                c[1]->reverse();
        }
    }
    inline bool not_root(void) { return fa && (fa->c[0] == this || fa->c[1] == this); }
    inline bool which(void) { return fa->c[1] == this; }
    inline void rotate()
    {
        Node *ffa = fa->fa;
        if (fa->not_root()) {
            ffa->c[fa->which()] = this;
        }
        bool ty = which();
        fa->c[ty] = c[!ty];
        if (fa->c[ty])
            fa->c[ty]->fa = fa;
        fa->update();
        c[!ty] = fa;
        fa->fa = this;
        fa = ffa;
        update();
    }
    inline void down(void)
    {
        static Node *st[N];
        static int cnt;
        cnt = 1;
        st[1] = this;
        for (Node *i = this; i->not_root(); i = i->fa)
            st[++cnt] = i->fa;//DEBUG
        for (; cnt; --cnt)
            st[cnt]->pushdown();
    }
    inline void splay(void)
    {
        down();
        while (not_root())
        {
            if (fa->not_root())
                ((fa->which() == which()) ? fa : this)->rotate();
            rotate(); //DEBUG
        }
    }
    Node *access(Node *ch = 0)
    {
        Node *p = 0;
        for (Node *x = this; x; p = x, x = x->fa)
        {
            x->splay();
            x->c[1] = p;
            x->update();
        }
        return p;
    }
    inline void make_root()
    {
        access()->reverse();
    }
    inline void link_to(Node *to)
    {
        make_root();
        if (to->find_root() == this)
            return;
        splay();
        fa = to;
    }
    inline void split_to(Node *bottom)
    {
        bottom->make_root();
        access();
        splay();
    }
    inline Node *find_root()
    {
        access();
        splay();
        Node *r = this;
        while (r->c[0])
            r = r->c[0];
        return r;
    }
    inline void cut(Node *another)
    {
        another->make_root();
        if (find_root() !=another)
            return;
        if (c[0] == 0 || another->fa != this)
            return;
        c[0] = another->fa = 0;
        update();
    }
}nd[N];

int main(void)
{
    int n = read, m = read;
    for (int i = 1; i <= n; ++i)
        nd[i].v = nd[i].s = read;
    while (m--)
    {
        int opt = read, x = read, y = read;
        switch (opt)
        {
        case 0:
            nd[x].split_to(nd + y);
            printf("%d\n", nd[x].s);
            break;
        case 1:
            nd[x].link_to(nd + y);
            break;
        case 2:
            nd[x].cut(nd + y);
            break;
        default:
            nd[x].splay();
            nd[x].v = y;
            nd[x].update();
            break;
        }
    }
}
点赞

发表评论

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