Link-Cut Tree 学习笔记

First Post:

Last Update:

Word Count:
2.6k

Read Time:
11 min

Page View: loading...

废话

系统的写一写不然忘了。

考虑树链剖分（或者更细化地、重链剖分），显然不支持删边，因为这样会破坏一整条链上的用于维持复杂度的信息，而我们并没有办法控制这样一条链的长度。

我们直接 非常草率地 使用 Splay 的思想：乱搞 均摊。我们现在把重链剖分的重儿子的定义换一下（常叫偏爱儿子），我们现在选择一条链的方式是：乱选。

姑且用着先，然后选择用一种美妙的数据结构来维护 既然使用了 Splay 的思想当然是 Splay 啦 。

然后再定义 怎么制仗的还有 维护的方式，我们定义一条树上剖出来的排好序的链对应的 Splay 是这条排好序的链使用某种优先级构建成的笛卡尔树是我们维护出来的 Splay ，这个优先级的具体值要看 Splay 的心情 搞不好就变成 Spaly 。

那么我们建树的过程大概就是，随便选择（比如第一个）儿子，然后随便搞成一条链形的 Splay 。

精神恍惚

好的我们重新用人话解释一下一棵 LCT 的样子。

首先，我们有一棵原树。

然后，我们随便选一个根（不过一般是 1 吧，反正初始化无所谓），然后给每一个点选择一个偏爱儿子（同重链剖分，不过没有具体要求），再把每个有偏爱边形成的链都变成一颗 Splay ，要求 Splay 的中序遍历恰好是对应的链的由下至上的遍历。

我们不需要太在意这些细节，一方面因为这是个势能结构（不然你肯定能见到可持久化 LCT 这种东西），到时候会有各种操作来打磨它的结构；另一方面是 LCT 既然支持加边，这种操作根本就不用实现。

总之，这样我们就得到了由 Splay 形成的森林。

不过我们还忽略了一个问题：Splay 的根的父亲是否需要值呢？

答案是肯定的，否则你没办法用这一堆森林还原出原树来，简单指向原树中这一条链的根的父亲即可。

这样由 Splay 内部的实边（这些边是需要 Splay 来维护的）与 Splay 之间的虚边（这些边是单独维护的）就形成了一棵树。

那么接下来，当我们要询问的时候，我们肯定要把询问的链单独拉出来，这样方便维护。

我们开始定义第一个操作：

access

这个操作的定义是，令某个结点到当前 LCT 的根的路径变成一条链，其余跟路径上的点有关系的边全部拆开。

1
2
3
4
5
void access(int x){
    for(int y=0;x;x=a[y=x].fa){
        splay(x);a[x].s[1]=y;pushup(x);
    }
}

看上去简短过头了，考虑它的意思。

首先，先把当前结点 旋转至 Splay 的根，那么显然的，它的左子树全都是它现在所在这条链，由它下行的部分，右子树则是由它上行的部分。

于是我们要砍掉左子树，将其赋为 .

接下来，我们要连接 与 在原树中的父亲，因为 已经是 Splay 的根了，所以其父亲就是其在原树中的父亲。这样，我们只需砍掉其父亲所在链中，由其父亲下行的部分，再接到当前结点即可。

发现这个操作与一开始的基本一致，我们把它的父亲旋至 Splay 的根，砍掉左子树，再把左儿子接过来。

在这个过程中不要忘记更新信息。

splay

多少还是提一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define iss(x) (a[a[x].fa].s[1]==x)

bool nroot(int x){
    return(a[a[x].fa].s[0]==x||iss(x));
}

void rotate(int x){
    int y=a[x].fa,k=iss(x),&ot=a[x].s[!k];
    if(nroot(y)) a[a[y].fa].s[iss(y)]=x;
    a[x].fa=a[y].fa;
    a[y].fa=x;a[y].s[k]=ot;
    a[ot].fa=y;ot=y;
    pushup(y);
}

void splay(int x){
    for(int y=st[st[0]=1]=x;nroot(y);st[++st[0]]=y=a[y].fa);
    for(;st[0];pushdown(st[st[0]--]));
    //下放标记

    for(int y=a[x].fa;nroot(x);rotate(x),y=a[x].fa)
        if(nroot(y)) rotate(iss(y)^iss(x)?x:y);
    pushup(x);
}

注意 LCT 有一些标记是需要下传的，但是 Splay 操作前因为不是自顶向下进入的，所以不能保证标记正确，于是我们需要手动将当前点到 Splay 的根上的所有标记自顶向下下放。

注意 rotate 操作要额外使用一个操作判读当前是否是 Splay 的根，因为 LCT 的特性。

因为 LCT 上只有一个结点没有父亲，判断其不为 Splay 的根是只需它是父亲的某个儿子。

makeroot

这是个有趣的操作。

你发现 access 并不能提取出所有的链，因为显然两个端点可能都不是根，所以我们需要造根。

1
2
3
4
void makeroot(int x){
    access(x);splay(x);
    flip(x);
}
1
2
3
4
void flip(int x){
    a[x].rev^=1;
    swap(a[x].s[0],a[x].s[1]);
}

考虑这为什么是对的。

首先，我们 access 联通了 与当前的根，并把 旋至 Splay 的根。

此时，因为 access 操作保证了整条链上 是深度最深的，而我们又将 旋转至了 Splay 的根，那么现在 的左子树为空。

此时我们将整个 Splay 左右翻转，即做到了右子树为空，即令 变为了 Splay 中深度最小的点，显然 没有父亲，此时 就为整个 LCT 的根。而其他结点的深度翻转，则反转了边的父子关系（注意这个改变不影响树的形态）。

至于不在这条链上的结点，它们的父亲没有改动。

那么此时，我们提取出树上 到 的链即：

1
2
3
4
void split(int x,int y){
    makeroot(x);access(y);
    splay(y);
}

注意最后的 splay 仅是为了维持平衡，因为它并没有改变什么东西，之后也没有操作。

findroot

既然我们可以随意换根，那么我们显然需要某种方式找到这个根。

简单的我们可以一路沿着父亲找上去，然后在根所在的 splay 中找到深度最小的结点（最左结点）。

不过为了平衡 偷懒 我们使用 access 与 splay 操作而非直接找父亲。

1
2
3
4
5
6
int findroot(int x){
    access(x);splay(x);
    for(;a[x].s[0];pushdown(x),x=a[x].s[0]);
    splay(x);
    return(x);
}

接下来，经过长长的铺垫我们终于来到看起来最重要的部分。

1
2
3
4
void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x) a[x].fa=y;
}

首先 makeroot 一下，然后 findroot 一下，这样就可以判断 与 是否联通。

1
2
3
4
5
6
7
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&a[y].fa==x&&!a[y].s[0]){
        a[y].fa=a[x].s[1]=0;
        pushup(x);
    }
}

首先，注意一下：

1
2
3
4
5
6
int findroot(int x){
    access(x);splay(x);
    for(;a[x].s[0];pushdown(x),x=a[x].s[0]);
    splay(x);
    return(x);
}

这里面是有一个 access 的。

首先 makeroot findroot 判断联通，然后你注意到，如果它们之间有边，那么 access 之后整条链一定只有它们两个点。所以 必然是 的父亲。

而且整条链上深度比 小的点只有 一个，且肯定是 的父亲，那么 左子树一定为空（显然右子树经过 access 后是空的）。

当然，因为整条链上只有两个点，所以维护了 size 的话也可以：

1
2
3
4
5
6
7
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&a[x].sz<3){
        a[y].fa=a[x].s[1]=0;
        pushup(x);
    }
}

有一个必须要提的地方，如果某些题目中没有 cut 那么维护连通性可以使用并查集以大幅减小常数。

CODE

此代码可以通过 P3690 【模板】动态树（Link Cut Tree） 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
struct LCT{
    int st[100010];
    struct node{
        int s[2],val,sum,fa;
        bool rev;
    }a[100010];
    #define iss(x) (a[a[x].fa].s[1]==x)
    void pushup(int x){
        a[x].sum=a[a[x].s[0]].sum^a[a[x].s[1]].sum^a[x].val;
    }
    void flip(int x){
        a[x].rev^=1;
        swap(a[x].s[0],a[x].s[1]);
    }
    void pushdown(int x){
        if(a[x].rev){
            flip(a[x].s[0]);
            flip(a[x].s[1]);
            a[x].rev=0;
        }
    }
    bool nroot(int x){
        return(a[a[x].fa].s[0]==x||iss(x));
    }
    void rotate(int x){
        int y=a[x].fa,k=iss(x),&ot=a[x].s[!k];
        if(nroot(y)) a[a[y].fa].s[iss(y)]=x;
        a[x].fa=a[y].fa;
        a[y].fa=x;a[y].s[k]=ot;
        a[ot].fa=y;ot=y;
        pushup(y);
    }
    void splay(int x){
        for(int y=st[st[0]=1]=x;nroot(y);st[++st[0]]=y=a[y].fa);
        for(;st[0];pushdown(st[st[0]--]));
        for(int y=a[x].fa;nroot(x);rotate(x),y=a[x].fa)
            if(nroot(y)) rotate(iss(y)^iss(x)?x:y);
        pushup(x);
    }
    void access(int x){
        for(int y=0;x;x=a[y=x].fa){
            splay(x);a[x].s[1]=y;pushup(x);
        }
    }
    void makeroot(int x){
        access(x);splay(x);
        flip(x);
    }
    int findroot(int x){
        access(x);splay(x);
        for(;a[x].s[0];pushdown(x),x=a[x].s[0]);
        splay(x);
        return(x);
    }
    void split(int x,int y){
        makeroot(x);
        access(y);splay(y);
    }
    void link(int x,int y){
        makeroot(x);
        if(findroot(y)!=x) a[x].fa=y;
    }
    void cut(int x,int y){
        makeroot(x);
        if(findroot(y)==x&&a[y].fa==x&&!a[y].s[0]){
            a[y].fa=a[x].s[1]=0;
            pushup(x);
        }
    }
}t;
char BuF[1<<26],*InF=BuF;
template<typename T>void read(T &x){
    bool f=1;
    for(;47>*InF||*InF>58;f^=*InF++=='-');
    for(x=0;47<*InF&&*InF<58;x=(x<<3)+(x<<1)+(*InF++^48));
    x=f?x:-x;
}
int main(){
    fread(BuF,1,1<<26,stdin);
    read(n);read(m);
    for(int i=1;i<=n;++i){
        read(t.a[i].val);
        t.a[i].sum=t.a[i].val;
    }
    for(int i=1,c,x,y;i<=m;++i){
        read(c);read(x);read(y);
        if(c==0){
            t.split(x,y);
            printf("%d\n",t.a[y].sum);
        }else if(c==1) t.link(x,y);
        else if(c==2) t.cut(x,y);
        else{
            t.splay(x);
            t.a[x].val=y;
            t.pushup(x);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return(0);
}

总结

LCT 现在应该不会考了，毕竟大纲放在那（

LCT 的时间复杂度均摊是 的，但实战中比重链剖分慢得多。能不用就别用这玩意，真心慢，各种细节多的很。

然后比重链剖分还有一个劣势，做不了子树问题，硬要做的话有限制而且复杂。

你要真想整一个完整版可以去学 Top Tree

嗯放道简单的习题在这：

NOI2014 魔法森林

≡