Eternity

Until The End

Link-Cut Tree

发表于 更新于 分类于 ，
本文字数： 15k 阅读时长 ≈ 14 分钟

“梦有归途，心有鸿鹄；所向之处，魂萦冢孤。”

顶级数据结构（指码量）。动态树的第一种，也是估计唯一要学的一种。

动态树

常见的动态树有 $\text{Link-Cut Tree,Euler Tour Tree}$ 和 $\text{Top Tree}$ 。

动态树是一类问题，动态树问题是指与森林有关的问题。

举个例子，写出一个可维护以下操作的数据结构：

  • 修改树上路径权值；
  • 查询树上路径权值；
  • 修改树上子树权值；
  • 查询树上子树权值。

这……树剖爆切。

再加两个操作：

  • 断边；
  • 连边。

保证依然是一棵树。则这棵树就是动态的，那么就需要一个能求解动态树问题的数据结构——$\text{Link/Cut Tree}$ 。

动态树问题

维护一个森林，支持删除某条边，加入某条边，并保证加边，删边之后仍是森林。我们要维护这个森林的一些信息。

一般的操作有两点连通性，两点路径权值和，连接两点和切断某条边、修改信息等。

链剖分

首先，我们应该知道，链的剖分不止一种。

有可用于树上区间问题的重链剖分，有可用于优化 $\text{dp}$ 的长链剖分，那么，接下来，也存在用于动态树问题的实链剖分。

实链剖分

由于动态维护一个森林，显然我们希望这个链是我们指定的链，以便利用来求解。对于一个点连向它所有儿子的边，我们自己选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边。对于实边，我们称它所连接的儿子为实儿子。对于一条由实边组成的链，我们同样称之为实链。

请记住我们选择实链剖分的最重要的原因：它是我们选择的，灵活且可变。正是它的这种灵活可变性，我们采用 $\text{Splay Tree}$ 来维护这些实链。

那么，对于 $\text{LCT}$ 的实现，我们就是用一些 $\text{Splay}$ 来动态维护实链剖分，以实现动态树问题的区间操作。并对每一条实链建 $\text{Splay}$ 树维护整个链区间的信息。

$\text{Link/Cut Tree}$ 的实现就是维护实链与虚链之间关系以达到维护整个森林的操作。

而 $\text{Splay}$ 维护所有实链，保证其中序遍历为维护的路径，这个性质极其重要，就如同树链剖分里保证了子树 $dfn$ 序和重链 $dfn$ 序一样。

LCT

实现

$\text{Link/Cut Tree}$ 本质上维护所有实边，用 $\text{Splay}$ 的前驱后继来维护原树中的父子关系。

而对于原树中的虚边，使用 $\text{Splay}$ 的根结点来维护。

辅助树

就像是后缀自动机里 $\text{Parent Tree}$ 和自动机的关系一样，这些 $\text{Splay}$ 构成了一棵辅助树，每一棵辅助树维护一棵原树，一些辅助树构成 $\text{LCT}$ ，并维护整个森林。

辅助树有以下性质：

  1. 辅助树由多棵 $\text{Splay}$ 组成，每棵 $\text{Splay}$ 维护原树中的一条路径，且中序遍历这棵 $\text{Splay}$ 得到的点序列，从前到后对应原树“从上到下”的一条路径。
  2. 原树每个节点与辅助树的 $\text{Splay}$ 节点一一对应。
  3. 辅助树的各棵 $\text{Splay}$ 之间并不是独立的。每棵 Splay 的根节点的父亲节点本应是空，但在 $\text{LCT}$ 中每棵 $\text{Splay}$ 的根节点的父亲节点指向原树中这条链的父亲节点（即链最顶端的点的父亲节点）。这类父亲链接与通常 $\text{Splay}$ 的父亲链接区别在于儿子认父亲，而父亲不认儿子，对应原树的一条虚边。因此，每个连通块恰好有一个点的父亲节点为空。
  4. 由于辅助树的以上性质，我们维护任何操作都不需要维护原树，辅助树可以在任何情况下拿出一个唯一的原树，我们只需要维护辅助树即可。

摘自 $\text{OI-Wiki}$ 。

原树与辅助树的结构关系

  • 原树中的实链 : 在辅助树中节点都在一棵 $\text{Splay}$ 中。
  • 原树中的虚链 : 在辅助树中，子节点所在 $\text{Splay}$的 Father 指向父节点，但是父节点的两个儿子都不指向子节点。
  • 注意：原树的根不等于辅助树的根。
  • 原树的 Father 指向不等于辅助树的 Father 指向。
  • 辅助树是可以在满足辅助树、$\text{Splay}$ 的性质下任意换根的。
  • 虚实链变换可以轻松在辅助树上完成，这也就是实现了动态维护树链剖分。

变量实意

chi[p][2] fa[p] sum[p] val[p] tag[p] laz[p] siz[p]
左右儿子的指针 父亲结点指针 路径权值和 点权 翻转标记 权值下传标记 辅助树子树大小

函数声明

通常函数

pushUp(p) ：向上传递。

pushDown(p) ：向下传递。

一般用于线段树或者平衡树里。

文艺平衡树（Splay 系函数）

getId(x) ：获取 $x$ 是父亲儿子的编号。

Splay(x) ：将 $x$ 旋转到当前 $\text{Splay}$ 的根结点。

rotate(x) ：Splay(x) 的具体操作，将 $x$ 向上旋转一层。

LCT 操作函数

Access(x) ：把从 $x$ 到根结点路径上所经过的所有结点加入实链，使 $x$ 到根的简单路径成为一条实路径，并放在同一 $\text{Splay}$ 里。

在实现 $\text{LCT}$ 时，只有 access(x) 操作是必要的，就如同在 $\text{Splay}$ 中的 Splay(x,k) 一样。其他操作都与题目本身息息相关。

isRoot(x) ：判断 $x$ 是否是所属 $\text{Splay}$ 树的根结点；。

update(x) ：用于 Access(x) 操作之后，以递归的方式从下到上 pushDown 更新树的信息。

makeRoot(x) ：使 $x$ 点成为其所在树的根。

link(u,v) ：加边。

cut(u,v) ：删边。

getAnc(x) ：求出 $x$ 所在树的根结点。

modifyX(x,v) ：修改 $x$ 的点权为 $v$ 。

split(u,v) ：提取 $(u,v)$ 的路径以区间操作。

函数实现

传递

1
2
3
4
5
inline void pushUp(int p)
{
    //其它信息。
    Tre[p].siz=Tre[ls].siz+Tre[rs].siz+1;
}
1
2
3
4
5
6
7
8
inline void pushDown(int p)
{
    if(Tre[p].tag!=-INF)
    {
        //传递。
        Tre[p].tag=-INF;
    }
}

平衡树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define getId(x) (chi[Fa[x]][1]==x)
inline void rotate(int x)
{
    int y=Tre[x].fa,z=Tre[y].fa,k=getId(x);
    if(!isRoot(y)) Tre[z].chi[Tre[z].chi[1]==y]=x;
    	//这句话是Splay没有的，因为特判isRoot
    Tre[y].chi[k]=Tre[x].chi[!k],Tre[y].fa=x,Tre[x].fa=z;
    Tre[x].chi[!k]=y,Tre[y].fa=x,Tre[x].fa=z;
    pushUp(y),pushUp(x);
}
inline void Splay(int x)
{
    update(x);
    //在Splay之前把旋转过的路径全部pushDown
    for(int fa;fa=Tre[x].fa,!isRoot(x);rotate(x))
        if(!isRoot(fa)) rotate(get(fa)==get(x)?fa:x);
}

LCT

判断根，这玩意儿其实可以不用函数，直接重定义也可：

1
#define isRoot(x) (Tre[Tre[x].fa].chi[0]!=x&&Tre[Tre[x].fa].chi[1]!=x)

这样做的原因是：因为 $\text{LCT}$ 有【如果一个儿子不是实儿子，他的父亲就不会指向他】的特性。所以，如果一个点不是他父亲的左右儿子所指，他就是当前 $\text{Splay}$ 的根。

虚实变换（access）

这是 $\text{LCT}$ 的核心操作，就好比求解一条由 $\text{Splay}$ 组成的路径。每一次直接调用结点信息即可。

access 的作用就是建立一条从 $(Rt,x)$ 的实链。

1
2
3
4
5
6
7
8
9
10
inline int Access(int x)
{
    int p;
    for(p=0;x;p=x,x=Tre[x].fa)
    {
        Splay(x);
        Tre[x].chi[1]=p;pushUp(x);
    }
    return p;
}

这个方法的实质就是从下向上逐步更新 $\text{Splay}$ ，把 $x$ 旋到当前 $\text{Splay}$ 的根。

为了保证辅助树（$\text{AuxTree}$）的性质，我们需要把 $x$ 之后的所有实边更改为虚边。还是因为有认父不认子的性质，我们直接把 $x$ 的子结点指向 $\text{Null}$ 。

这个过程不太好叙述，所以可以去 $\text{Oi-Wiki}$ 看一下过程。

Access(x) 的操作可以概括为四步：

  1. 把 $x$ 旋转到根结点；
  2. 把其子结点换成之前结点；
  3. 更新当前结点的维护信息；
  4. 把当前结点换成当前结点的父结点，继续操作。

这里的 Access(x) 会返回一个 int 值，这个返回值代表的是最后一次虚实链变换时，虚边父亲结点的编号。这个值的含义有：

  • 连续两次 Access 操作时，第二次返回的值是两次 Access 结点的 $\text{LCA}$ ；
  • 这个值也表示 $x$ 到根所在的链中的 $\text{Splay}$ 树的根结点。而这个结点会被旋转到根结点，所以其父结点是 $\text{Null}$ 。

Splay(x) 中的 update(x) 操作：

1
2
3
4
5
void update(int p)
{
    if(!isRoot(p)) update(Tre[p].fa);
    pushDown(p);
}

makeRoot(x)

话说这个函数的作用和 Access(x) 一样重要。在维护信息时，会出现路径深度无法严格递增的情况，这是不能够出现在 $\text{Splay}$ 树中的。

而 makeRoot(x) 的作用就是指定的结点成为原树的根。

我们已知，在 Access(x) 中的返回值就是当前 $\text{Splay}$ 的根，而 $x$ 到当前根的路径就会恰好构成一棵 $\text{Splay}$ 树，且根结点已知。（设为 $y$ ）

考虑将树用有向图表示，并把树的无向边修改为有向边，并从子结点到父结点。然后仔细思考，对于换根操作，就是把 $x$ 到 $y$ 的路径的边全部反向。

可以知道，无论如何反转路径，都不会影响整棵树的拓扑结构，且不会影响其他结点的偏序关系。

然后，将 $x$ 到当前根 $y$ 的路径翻转，就是 makeRoot(x) 的操作。

而 $y$ 就是 $x$ 到当前根的路径所代表的 $\text{Splay}$ 的根，所以把以 $y$ 为根的 $\text{Splay}$ 的树进行区间翻转即可。

1
2
3
4
5
6
inline void makeRoot(int p)
{
    p=Access(p);
    std::swap(Tre[p].chi[0],Tre[p].chi[1]);
    tag[p]^=1;
}

link(u,v)

连边，首先执行 makeRoot(u) ，然后把 $u$ 的父结点指向 $v$ ，但这个操作不可能发生在同一棵树上，所以需要先执行一次 Splay(x) 。

1
2
3
4
5
inline void link(int u,int v)
{
    makeRoot(u);Splay(u);
    Tre[u].fa=v;
}

cut(u,v)

如果我们要删除一条边，肯定首先这条边得存在才能算合法。

如果题目保证合法，我们就不需要特判一次，直接 split(u,v) ，这时候 $v $ 是提取的根结点，而 $x$ 是它的子结点，然后直接双向断开。

1
2
3
4
5
inline void cut(int u,int v)
{
    makeRoot(u),Access(v),Splay(v);
    Tre[v].chi[0]=Tre[u].fa=0;
}

而对于不保证合法，可以用一个 std::map 来存储。

边存在的性质：

  1. $(x,y)$ 连通；
  2. $(x,y)$ 路径上没有其它链存在；
  3. $x$ 没有右儿子。

然后 $(x,y)$ 就存在边。

split(u,v)

操作意义是，拿出一棵 $\text{Splay}$ 树，然后维护 $(u,v)$ 路径。将 $(u,v)$ 之间的路径变成实边路径。

这个操作使 $(u,v)$ 路径保证在 $v$ 的子树上，就可以轻松解决一些问题。

1
2
3
4
inline void split(int u,int v)
{
    makeRoot(u),Access(v),Splay(v);
}

然后你会发现这代码很好打，所以一般而言不会打出 split(u,v) 的函数形式，直接一键三连带走。

getAnc(p)

找到当前辅助树上的根，在 Access(p) 后再 Splay(p) 即可，这样根就是树里最小的那个，沿着左子树一直 pushDown 即可，最后再次 Splay(p) 以保证复杂度。

1
2
3
4
5
6
7
inline int getAnc(int p)
{
    Access(p),Splay(p),pushDown(p);
    while(Tre[p].chi[0]) p=Tre[p].chi[0],pushDown(p);
    Splay(p);
    return p;
}

还有三点应该知道，以免暴毙的：

  1. 一定要记得在应该执行的时候执行 pushUp() 和 pushDown() ，$\text{LCT}$ 的这两步不同于 $\text{SegmentTree}$ ，如果少执行一次，并不仅仅是影响答案，还可能把修改改到不该改的点上。（深知 $\text{Dyd}$ 没有 pushDown 而调半天的经历）
  2. 其 rotate 和文艺平衡树的区别。
  3. 因为这里的 $\text{Splay}$ 只是一个辅助工具，所以不存在不旋转的根的情况，所以不需要传第二个参数。

例题

维护树链

Tree II

不愧它有个 $\text{II}$ 的名字，这道题乍一看就是在《线段树2》的操作放在树上并加上改边操作。

然后就打了一遍 $\text{LCT}$ 的板子。

AC Code 
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define int long long
typedef long long ll;
const int MAXN=1e5+10;
const int Mod=51061;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,Q;
namespace LCT
{
    struct LC
    {
        int chi[2],fa,siz,val,sum,add,mul,rev;
            //子结点，父结点，点权值，区间权值和
            //加法标记，乘法标记，翻转标记
        #define chi(p,i) Tre[p].chi[i]
        #define fa(p) Tre[p].fa
        #define siz(p) Tre[p].siz
        #define val(p) Tre[p].val
        #define sum(p) Tre[p].sum
        #define add(p) Tre[p].add
        #define mul(p) Tre[p].mul
        #define rev(p) Tre[p].rev
    }Tre[MAXN];
    inline void clear(int p)
    {
        /*LC *t = &Tre[0];
        t->chi*/
        chi(p,0)=chi(p,1)=fa(p)=siz(p)=val(p)=sum(p)=rev(p)=add(p)=0;
        mul(p)=1;
    }
    /*inline rot(int x)
    {
        y = fa[x], z = fa[y];
        int k = ch[y][1] == x;
        ch[fa[x] = z][ch[z][1] == y] = x;
        fa[ch[x][k ^ 1]] = y, ch[y][k] = ch[x][k ^ 1];
        fa[y] = x, ch[x][k ^ 1] = y;
    }*/
    inline int getId(int p)
    {
        return (chi(fa(p),1)==p);
    }
    inline int isRoot(int p)
    {
        clear(0);
        return chi(fa(p),0)!=p&&chi(fa(p),1)!=p;
    }
    inline void pushUp(int p)   //mainTain(p)
    {
        clear(0);
        siz(p)=(siz(chi(p,0))+siz(chi(p,1))+1)%Mod;
        sum(p)=(sum(chi(p,0))+sum(chi(p,1))+val(p))%Mod;
    }   
    inline void pushDown(int p) //和线段树2类似，需要传两个tag
                                //且要注意顺序。
    {
        clear(0);
        if(mul(p)!=1)
        {
            if(chi(p,0))        //存在左儿子
            {
                mul(chi(p,0))=(mul(chi(p,0))*mul(p))%Mod;
                val(chi(p,0))=(val(chi(p,0))*mul(p))%Mod;
                sum(chi(p,0))=(sum(chi(p,0))*mul(p))%Mod;
                add(chi(p,0))=(add(chi(p,0))*mul(p))%Mod;
            }
            if(chi(p,1))        //存在右儿子
            {
                mul(chi(p,1))=(mul(chi(p,1))*mul(p))%Mod;
                val(chi(p,1))=(val(chi(p,1))*mul(p))%Mod;
                sum(chi(p,1))=(sum(chi(p,1))*mul(p))%Mod;
                add(chi(p,1))=(add(chi(p,1))*mul(p))%Mod;
            }
            mul(p)=1;
        }
        if(add(p))              //同上
        {
            if(chi(p,0))
            {
                add(chi(p,0))=(add(chi(p,0))+add(p))%Mod;
                val(chi(p,0))=(val(chi(p,0))+add(p))%Mod;
                sum(chi(p,0))=(sum(chi(p,0))+add(p)*siz(chi(p,0))%Mod)%Mod;
            }
            if(chi(p,1))
            {
                add(chi(p,1))=(add(chi(p,1))+add(p))%Mod;
                val(chi(p,1))=(val(chi(p,1))+add(p))%Mod;
                sum(chi(p,1))=(sum(chi(p,1))+add(p)*siz(chi(p,1))%Mod)%Mod;
            }
            add(p)=0;
        }
        if(rev(p))
        {
            if(chi(p,0)) rev(chi(p,0))^=1,std::swap(chi(chi(p,0),0),chi(chi(p,0),1));
            if(chi(p,1)) rev(chi(p,1))^=1,std::swap(chi(chi(p,1),0),chi(chi(p,1),1));
            rev(p)=0;
        }
    }
    inline void update(int p)
    {
        if(!isRoot(p)) update(fa(p));
        pushDown(p);
    }
    inline void printOut(int p) //中序遍历
    {
        if(!p) return ;
        pushDown(p);
        printOut(chi(p,0));
        write(p),puts("");
        printOut(chi(p,1));
    }
    inline void rotate(int x)
    {
        int y=fa(x),z=fa(y),k=getId(x);
        fa(x)=z;
        if(!isRoot(y)) chi(z,getId(y))=x;
        chi(y,k)=chi(x,k^1),fa(chi(x,k^1))=y;
        chi(x,k^1)=y,fa(y)=x;
        pushUp(y),pushUp(x),pushUp(z);
    }
    inline void Splay(int p)
    {
        update(p);
        for(int f=fa(p);f=fa(p),!isRoot(p);rotate(p))
            if(!isRoot(f)) rotate(getId(p)==getId(f)?f:p);
    }
    inline void Access(int p)
    {
        for(int f=0;p;f=p,p=fa(p)) Splay(p),chi(p,1)=f,pushUp(p);
    }
    inline void makeRoot(int p)
    {
        Access(p),Splay(p);
        std::swap(chi(p,0),chi(p,1));
        rev(p)^=1;
    }
    inline int getAnc(int p)
    {
        Access(p),Splay(p);
        while(chi(p,0)) p=chi(p,0);
        Splay(p);
        return p;
    }
};
char opt[10];
int Qu,Qv,Qc;
signed main()
{
    // freopen("LCT.in","r",stdin);
    // freopen("LCT.out","w",stdout);
    read(N,Q);
    for(re int i=1;i<=N;++i) LCT::val(i)=1,LCT::pushUp(i);
    for(int i=1,u,v;i<N;++i)
    {
        read(u,v);
        if(LCT::getAnc(u)!=LCT::getAnc(v))
            LCT::makeRoot(u),LCT::fa(u)=v;
    }
    while(Q--)
    {
        scanf("%s",opt+1);
        if(opt[1]=='+')
        {
            read(Qu,Qv,Qc);
            LCT::makeRoot(Qu),LCT::Access(Qv),LCT::Splay(Qv);
            LCT::val(Qv)=(LCT::val(Qv)+Qc)%Mod;
            LCT::sum(Qv)=(LCT::sum(Qv)+LCT::siz(Qv)*Qc%Mod)%Mod;
            LCT::add(Qv)=(LCT::add(Qv)+Qc)%Mod;
        }
        if(opt[1]=='-')
        {
            read(Qu,Qv);
            LCT::makeRoot(Qu),LCT::Access(Qv),LCT::Splay(Qv);
            if(LCT::chi(Qv,0)==Qu&&!LCT::chi(Qu,1))
                LCT::chi(Qv,0)=LCT::fa(Qu)=0;
            read(Qu,Qv);
            if(LCT::getAnc(Qu)!=LCT::getAnc(Qv))
                LCT::makeRoot(Qu),LCT::fa(Qu)=Qv;
        }
        if(opt[1]=='*')
        {
            read(Qu,Qv,Qc);
            LCT::makeRoot(Qu),LCT::Access(Qv),LCT::Splay(Qv);
            LCT::val(Qv)=LCT::val(Qv)*Qc%Mod;
            LCT::sum(Qv)=LCT::sum(Qv)*Qc%Mod;
            LCT::mul(Qv)=LCT::mul(Qv)*Qc%Mod;
        }
        if(opt[1]=='/')
        {
            read(Qu,Qv);
            LCT::makeRoot(Qu),LCT::Access(Qv),LCT::Splay(Qv);
            write(LCT::sum(Qv)),puts("");
        }
    }
    return 0;
}
/*
3 2
1 2
2 3
* 1 3 4
/ 1 1
*/

【模板】

用了 $\text{Yxc}$ 的板子，重新学习了一下 $\text{Link/Cut Tree}$ 。

$\text{Au}$ 爷说得对，如果只是抄笔记的话，不会有任何结果，无论是哪个学科都是这样的。

所有的核心操作在这道题里都体现了，也没有什么额外的操作，所以可以拿来当板子背。

AC Code 
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=1e5+10;
int N,M;
struct Tre
{
    int chi[2],fa,val;
    int sum,rev;
}Tr[MAXN];
int Stk[MAXN];
#define ls(p) Tr[p].chi[0]
#define rs(p) Tr[p].chi[1]
inline void pushRev(int p)
{
    std::swap(Tr[p].chi[0],Tr[p].chi[1]);
    Tr[p].rev^=1;
}
inline void pushUp(int p)
{
    Tr[p].sum=Tr[ls(p)].sum^Tr[rs(p)].sum^Tr[p].val;
}
inline void pushDown(int p)
{
    if(Tr[p].rev)
    {
        pushRev(ls(p)),pushRev(rs(p));
        Tr[p].rev=0;
    }
}
inline bool isRoot(int p)
{
    return ls(Tr[p].fa)!=p&&rs(Tr[p].fa)!=p;
}
inline void rotate(int x)
{
    int y=Tr[x].fa,z=Tr[y].fa;
    int k=rs(y)==x;
    if(!isRoot(y)) Tr[z].chi[rs(z)==y]=x;
    Tr[x].fa=z;
    Tr[y].chi[k]=Tr[x].chi[k^1],Tr[Tr[x].chi[k^1]].fa=y;
    Tr[x].chi[k^1]=y,Tr[y].fa=x;
    pushUp(y),pushUp(x);
}
inline void Splay(int x)
{
    int r=x,Top=0;
    Stk[++Top]=r;
    while(!isRoot(r)) Stk[++Top]=r=Tr[r].fa;
    while(Top) pushDown(Stk[Top--]);
    while(!isRoot(x))
    {
        int y=Tr[x].fa,z=Tr[y].fa;
        if(!isRoot(y))
            if((rs(y)==x)^(rs(z)==y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}
//建立从根到x的路径，并将x变成Splay的根结点
inline void access(int x)
{
    int z=x;
    for(int y=0;x;y=x,x=Tr[x].fa)
    {
        Splay(x);
        rs(x)=y,pushUp(x);
    }
    Splay(z);
}
//将x变成原树的根结点
inline void makeRoot(int x)
{
    access(x);
    pushRev(x);
}
//找到当前x所在原树的根结点，并把原树的根结点旋转到Splay的根结点
inline int findRoot(int x)
{
    access(x);
    while(ls(x)) pushDown(x),x=ls(x);
    Splay(x);
    return x;
}
//在x到y中的路径中建立一个Splay，其根结点为y
inline void split(int x,int y)
{
    makeRoot(x);
    access(y);
}
//如果x,y不连通，加入边(x,y)
inline void link(int x,int y)
{
    makeRoot(x);
    if(findRoot(y)!=x) Tr[x].fa=y;
}
//如果x,y连通，删除边(x,y)
inline void cut(int x,int y)
{
    makeRoot(x);
    if(findRoot(y)==x&&Tr[y].fa==x&&!ls(y))
    {
        rs(x)=Tr[y].fa=0; 
        pushUp(x);
    }
}
int main()
{
    // freopen("Link_Cut Tree.in","r",stdin);
    // freopen("Link_Cut Tree.out","w",stdout);
    read(N,M);
    for(int i=1;i<=N;++i) read(Tr[i].val);
    for(int opt,x,y;M--;)
    {
        read(opt,x,y);
        if(opt==0)
        {
            split(x,y);
            write(Tr[y].sum),puts("");
        }
        else if(opt==1) link(x,y);
        else if(opt==2) cut(x,y);
        else
        {
            Splay(x);
            Tr[x].val=y;
            pushUp(x);
        }
    }
    return 0;
}
/*
3 3 
1
2
3
1 1 2
0 1 2 
0 1 1
*/

维护连通性质

这个真的很简单，写了几篇这个题解，然后就忘记在这里更新了。

然后看了一下以前自学写的笔记，感觉不如听 $\text{Yxc}$ 的好，板子也背的是 $\text{Yxc}$ 的。

对于判断 $u,v$ 是否连通，就直接返回 findRoot(u)==findRoot(v) 即可。

其中 #define findRoot() getAnc() 。（一个是老码风，一个是新码风）

例题的话，可以是P2147洞穴勘测和P3950部落冲突，都非常的板子。

相关文章