给定 $n$ 个点、每个点的权值和 $m$ 次操作：
0 x y代表询问从 $x$ 到 $y$ 的路径上的点的权值的 $\operatorname{xor}$ 和。保证 $x$ 到 $y$ 是联通的。1 x y代表连接 $x$ 到 $y$，若 $x$ 到 $y$ 已经联通则无需连接。2 x y代表删除边 $(x,y)$，不保证边 $(x,y)$ 存在。3 x y代表将点 $x$ 上的权值变成 $y$。$1\leq n\leq 10^5,1\leq m\leq3\times10^5$。
本文中维护信息，以维护路径异或和为例。
动态树问题
考虑树链剖分可以维护树上路径信息和子树信息，但是树的形态是静态的。如果树的形态会发生改变，那么树链剖分就必须重构。
当树的形态发生改变时，这种问题，就称之为动态树问题。
事实上，动态树问题处理的是若干棵树构成的森林。
Link Cut Tree
其实 LCT 是一个比较暴力的结构，复杂度纯粹源于势能均摊。
下文的 Splay 节点都基于：
1
2
3
4
5
struct node{
int value;
int sum,father,child[2];
bool reverse;
}t[N+1];
实链剖分
仍然考虑将树剖为链来处理，但是重链剖分和长链剖分都不太适合。因为树的形态会发生改变，子树大小、子树高度都会随着树的形态改变而改变。
因此我们引入一种新的剖分方式——实链剖分。
实链剖分就是随便剖。——xxy
对于一个点，我们自行指定一个子节点为实儿子连实边，其余子节点均为虚儿子，连虚边。
对于实边组成的链，称之为实链，用一棵 Splay 树维护一条实链的链区间。
正因为实链剖分是随便剖，因此实边、虚边对于原本需要维护的信息没有什么影响，可以随便改。
辅助树
对于一棵原树，将其实链剖分后可以建立其辅助树。例如：
其辅助树为：
每条原树上的实链都对应辅助树上的一棵 Splay。辅助树上同样分实边、虚边：
- Splay 内部的边为实边，对应原树上的实边。
- Splay 外部的边为虚边，只从 Splay 的根节点指向原树上实边顶部节点的父节点，虚边是单向的。
LCT 通过这样的辅助树来维护实链信息，进而维护原树的信息，因为辅助树可以维护原树的所有信息，且辅助树上更容易实现实边、虚边的转化。
记 $\operatorname{child}_0(x),\operatorname{child}_1(x)$ 分别为 $x$ 在辅助树上的左、右子节点，$\operatorname{father}(x)$ 为 $x$ 在辅助树上的父节点。
Splay 函数操作
显然，维护了若干棵 Splay。此部分针对的节点信息都是 Splay 上的信息，而不是辅助树上的，也不是原树上的。
check
判断是左子节点还是右子节点。
1
2
3
bool check(int p){
return t[t[p].father].child[1]==p;
}
isRoot
用于判断是否为 Splay 的根，根据虚边父节点不认子节点判断即可。
1
2
3
bool isRoot(int p){
return t[t[p].father].child[0]!=p&&t[t[p].father].child[1]!=p;
}
up
维护 Splay 子树信息。
1
2
3
void up(int p){
t[p].sum=t[t[p].child[0]].sum^t[p].value^t[t[p].child[1]].sum;
}
down
下传标记。
LCT 一般都需要额外维护区间翻转标记。
1
2
3
4
5
6
7
8
void down(int p){
if(t[p].reverse){
t[t[p].child[0]].reverse^=1;
t[t[p].child[1]].reverse^=1;
swap(t[p].child[0],t[p].child[1]);
t[p].reverse=false;
}
}
update
如果没有下放标记，你把 down 写在 rotate 里面是错的，因为标记要从上往下下放，不然你下放了又有新的。因此在 LCT 的 splay 操作前，需要调用 update 来将根节点至当前节点路径上所有的标记都下放。
（在 Splay 维护区间操作中，因为你找到对应节点的时候已经顺便下放了标记，所以没有 update。）
递归寻找即可。
1
2
3
4
5
6
void update(int p){
if(!isRoot(p)){
update(t[p].father);
}
down(p);
}
rotate
同 Splay，唯一细节是需要通过 isRoot(y) 来判断 $y$ 是否为根，从而判断是否应当更新 $y$ 的父节点 $z$ 的子节点信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void rotate(int x){
int y=t[x].father,z=t[y].father;
bool mode=check(x);
t[y].child[mode]=t[x].child[!mode];
t[x].child[!mode]=y;
if(!isRoot(y)){
t[z].child[check(y)]=x;
}
if(t[y].child[mode]){
t[t[y].child[mode]].father=y;
}
t[y].father=x;
t[x].father=z;
up(y);
up(x);
}
splay
splay 之前 update 一下即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void splay(int x){
update(x);
while(!isRoot(x)){
int p=t[x].father;
if(isRoot(p)){
rotate(x);
break;
}
if(check(p)==check(x)){
rotate(p);
rotate(x);
}else{
rotate(x);
rotate(x);
}
}
}
LCT 函数操作
access
LCT 的核心操作之一。
记原树的根为 $\textit{root}$，access(x) 用于将 $\textit{root}\sim x$ 路径上的所有点放入一棵 Splay，即将 $x\sim\textit{root}$ 这条路径变成实链，并将其他原来与这条路径相连的实边都变成虚边。
同样以上文的树为例：
其辅助树为：
以 access(N) 为例，则我们希望原树变为：
最终，我们得到的实链为：$A\rightarrow C\rightarrow G\rightarrow H\rightarrow I\rightarrow L\rightarrow N$。
考虑 Splay 维护的是原树上的实链，中序遍历是从上至下。 $N$ 和实链上下一个节点连了实边，要换成虚边；但是整个右子树都可以丢掉，因此直接断开 $N$ 和 $\operatorname{child}_1(N)=O$（此部分接下来的图均为辅助树）：
之后我们希望把 $L\rightarrow N$ 这一段实链接到 $N$ 的父节点 $I$ 的实链上，从而得到 $I\rightarrow L\rightarrow N$ 的一条实链。
先将 $I$ splay 到根，之后 $I$ 所在 Splay 的左子树即向上实链的一部分，右子树直接丢掉，换为 $N$。
循环往复：
最终，access 的操作策略即：
- 对于 $\operatorname{access}(x)$，初始维护 $p=0$；
- 将 $x$
splay到根； - 令 $\operatorname{child}_1(x)\leftarrow p$；
- 更新 $x$ 的子树信息，即调用
up； - 令 $p\leftarrow x,x\leftarrow\operatorname{father}(x)$。
1
2
3
4
5
6
7
void access(int x){
for(int p=0;x;p=x,x=t[x].father){
splay(x);
t[x].child[1]=p;
up(x);
}
}
makeRoot
我们现在已经可以通过 access 实现 $\textit{root}\sim x$ 的路径信息维护，但是往往我们需要维护的路径 $u\sim v$ 并不是根节点到另一个节点的路径。我们考虑强行给原树换根，这样就可以通过 access 操作之后很好用 Splay 树维护。
对 $x$ 进行 makeRoot 的流程：
-
先对其进行
access操作，得到 $\textit{root}\rightarrow x$ 的一条实链； -
之后把 $x$
splay到 Splay 树的根，等价于将其换为了原树的根节点； -
但是这样使得原来 $\textit{root}\rightarrow x$ 的实链的父子关系「上下颠倒」，因此需要对这棵 Splay 进行整体区间翻转操作。打上一个翻转标记即可。
其实颠倒对于辅助树是没有什么影响的，因为辅助树的实边是无向的；但是，原树的边是有向的，强行换根会导致父子关系颠倒，所以需要区间翻转。
（如果对于区间翻转还看不懂，可以看到下文
find再想一想。）
1
2
3
4
5
6
void makeRoot(int x){
access(x);
splay(x);
t[x].reverse^=1;
swap(t[x].child[0],t[x].child[1]);
}
find
find 用于查找节点 $x$ 所在原树的根节点 $\textit{root}$。
access 得到 $\textit{root}\rightarrow x$ 的实链，之后把 $x$ splay 到根节点，再一直走左子节点求最小即可。
需要 splay 操作来保证复杂度。
1
2
3
4
5
6
7
8
9
10
11
int find(int x){
access(x);
splay(x);
down(x);
while(t[x].child[0]){
x=t[x].child[0];
down(x);
}
splay(x);
return x;
}
为什么 find 不需要打翻转标记
考虑 find 并没有改变原树根——尽管都执行了 access 和 splay。
事实上，LCT 也没有真正维护过原树根，这是一个比较抽象的概念。
makeRoot 需要打翻转标记，是因为强行换根为 $x$ 之后，实际上 $x$ 还有祖先节点——即其左子树，这时，应当将其放入右子树内，成为其子节点。
split
split 用于提取任意两点 $u,v$ 之间的路径成为一棵 Splay。
对 $u$ makeRoot，之后再对 $v$ 进行 access 操作即可。
需要对 $v$ 进行 splay 操作来保证复杂度。特别地，在此之后 $u\sim v$ 路径信息便对应以 $v$ 为根的 Splay，信息都在 $v$ 上面。
1
2
3
4
5
void split(int u,int v){
makeRoot(u);
access(v);
splay(v);
}
link
考虑任意连边 $(u,v)$ 不好做，先对 $u$ makeRoot，使其成为原树根。之后考虑 $v$ 是否在 $u$ 子树内，通过 find 操作即可判断。
否则，$u$ 已经没有父节点，直接把 $u$ 挂在 $v$ 子树上，连虚边即可。这也就是实链剖分的好处——随便剖。
1
2
3
4
5
6
void link(int u,int v){
makeRoot(u);
if(find(v)!=u){
t[u].father=v;
}
}
cut
同理，先对 $u$ makeRoot，之后就是判断边 $(u,v)$ 存在。
由于我们维护的是辅助树，因此判断边有些麻烦，充要条件为：$\operatorname{find}(v)=u\land\operatorname{father}(v)=u\land\operatorname{child}_0(v)=0$。
-
$\operatorname{find}(v)=u$：$v$ 在 $u$ 原树的子树内，即 $u,v$ 连通。
-
$\operatorname{father}(v)=u\land\operatorname{child}_0(v)=0$：考虑
makeRoot后，$u$ 是 Splay 的根，$u$ 没有左子树。此时，$v$ 要紧跟在 $u$ 后面，$u\rightarrow v$ 中间不能有，$v$ 的左子树也不能有。
1
2
3
4
5
6
void cut(int u,int v){
makeRoot(u);
if(find(v)==u&&t[v].father==u&&!t[v].child[0]){
t[v].father=t[u].child[1]=0;
}
}
维护信息操作
单点操作
考虑我们不想上传更新，因此直接 makeRoot 之后单点操作即可。
1
2
3
4
void set(int x,int k){
makeRoot(x);
t[x].value=k;
}
路径操作
split 之后操作 Splay 根节点信息即可。
1
2
3
4
int query(int u,int v){
split(u,v);
return t[v].sum;
}
时间复杂度
不会势能，懒得学。
总之，是 $\mathcal O(m\log n)$ 的。
Luogu P3690 动态树（LCT） AC 代码
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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5;
int n;
struct LCT{
struct node{
int value;
int sum,father,child[2];
bool reverse;
}t[N+1];
bool check(int p){
return t[t[p].father].child[1]==p;
}
bool isRoot(int p){
return t[t[p].father].child[0]!=p&&t[t[p].father].child[1]!=p;
}
void up(int p){
t[p].sum=t[t[p].child[0]].sum^t[p].value^t[t[p].child[1]].sum;
}
void down(int p){
if(t[p].reverse){
t[t[p].child[0]].reverse^=1;
swap(t[t[p].child[0]].child[0],t[t[p].child[0]].child[1]);
t[t[p].child[1]].reverse^=1;
swap(t[t[p].child[1]].child[0],t[t[p].child[1]].child[1]);
t[p].reverse=false;
}
}
void update(int p){
if(!isRoot(p)){
update(t[p].father);
}
down(p);
}
void rotate(int x){
int y=t[x].father,z=t[y].father;
bool mode=check(x);
t[y].child[mode]=t[x].child[!mode];
t[x].child[!mode]=y;
if(!isRoot(y)){
t[z].child[check(y)]=x;
}
if(t[y].child[mode]){
t[t[y].child[mode]].father=y;
}
t[y].father=x;
t[x].father=z;
up(y);
up(x);
}
void splay(int x){
update(x);
while(!isRoot(x)){
int p=t[x].father;
if(isRoot(p)){
rotate(x);
break;
}
if(check(p)==check(x)){
rotate(p);
rotate(x);
}else{
rotate(x);
rotate(x);
}
}
}
void access(int x){
for(int p=0;x;p=x,x=t[x].father){
splay(x);
t[x].child[1]=p;
up(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
t[x].reverse^=1;
swap(t[x].child[0],t[x].child[1]);
}
int find(int x){
access(x);
splay(x);
down(x);
while(t[x].child[0]){
x=t[x].child[0];
down(x);
}
splay(x);
return x;
}
void split(int u,int v){
makeRoot(u);
access(v);
splay(v);
}
int query(int u,int v){
split(u,v);
return t[v].sum;
}
void link(int u,int v){
makeRoot(u);
if(find(v)!=u){
t[u].father=v;
}
}
void cut(int u,int v){
makeRoot(u);
if(find(v)==u&&t[v].father==u&&!t[v].child[0]){
t[v].father=t[u].child[1]=0;
}
}
void set(int x,int k){
makeRoot(x);
t[x].value=k;
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
t.set(i,x);
}
while(m--){
int op,x,y;
cin>>op>>x>>y;
switch(op){
case 0:
cout<<t.query(x,y)<<'\n';
break;
case 1:
t.link(x,y);
break;
case 2:
t.cut(x,y);
break;
case 3:
t.set(x,y);
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
维护路径信息
一棵 $n$ 个点的树，每个点的初始权值为 $1$。
对于这棵树有 $q$ 个操作，每个操作为以下四种操作之一：
+ u v c：将 $u$ 到 $v$ 的路径上的点的权值都加上自然数 $c$；- u1 v1 u2 v2：将树中原有的边 $(u_1,v_1)$ 删除，加入一条新边 $(u_2,v_2)$，保证操作完之后仍然是一棵树；* u v c：将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$；/ u v：询问 $u$ 到 $v$ 的路径上的点的权值和，将答案对 $51061$ 取模。对于 $100\%$ 的数据，$1\leq n,q\leq10^5$，$0\leq c\leq10^4$。
对于 Splay 上的节点，维护加法、乘法标记和子树和即可。
唯一需要注意的是，$0$ 号节点的信息不要动，不然你就只能特判子节点为空。（事实上，本题不需要。原因见此。）
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=1e5,P=51061;
int n;
struct LCT{
struct node{
int value;
int sum,size,father,child[2];
bool reverse;
int mul,add;
}t[N+1];
void build(){
for(int i=1;i<=n;i++){
t[i].size=t[i].value=t[i].sum=t[i].mul=1;
}
}
bool check(int p){
return t[t[p].father].child[1]==p;
}
bool isRoot(int p){
return t[t[p].father].child[0]!=p&&t[t[p].father].child[1]!=p;
}
void up(int p){
t[p].sum=(t[t[p].child[0]].sum+t[p].value+t[t[p].child[1]].sum)%P;
t[p].size=t[t[p].child[0]].size+1+t[t[p].child[1]].size;
}
void down(int p){
if(t[p].reverse){
t[t[p].child[0]].reverse^=1;
swap(t[t[p].child[0]].child[0],t[t[p].child[0]].child[1]);
t[t[p].child[1]].reverse^=1;
swap(t[t[p].child[1]].child[0],t[t[p].child[1]].child[1]);
t[p].reverse=false;
}
if(t[p].mul!=1){
t[t[p].child[0]].mul=1ll*t[t[p].child[0]].mul*t[p].mul%P;
t[t[p].child[0]].add=1ll*t[t[p].child[0]].add*t[p].mul%P;
t[t[p].child[0]].value=1ll*t[t[p].child[0]].value*t[p].mul%P;
t[t[p].child[0]].sum=1ll*t[t[p].child[0]].sum*t[p].mul%P;
t[t[p].child[1]].mul=1ll*t[t[p].child[1]].mul*t[p].mul%P;
t[t[p].child[1]].add=1ll*t[t[p].child[1]].add*t[p].mul%P;
t[t[p].child[1]].value=1ll*t[t[p].child[1]].value*t[p].mul%P;
t[t[p].child[1]].sum=1ll*t[t[p].child[1]].sum*t[p].mul%P;
t[p].mul=1;
}
if(t[p].add){
t[t[p].child[0]].add=(t[t[p].child[0]].add+t[p].add)%P;
t[t[p].child[0]].value=(t[t[p].child[0]].value+t[p].add)%P;
t[t[p].child[0]].sum=(t[t[p].child[0]].sum+1ll*t[t[p].child[0]].size*t[p].add)%P;
t[t[p].child[1]].add=(t[t[p].child[1]].add+t[p].add)%P;
t[t[p].child[1]].value=(t[t[p].child[1]].value+t[p].add)%P;
t[t[p].child[1]].sum=(t[t[p].child[1]].sum+1ll*t[t[p].child[1]].size*t[p].add)%P;
t[p].add=0;
}
}
void update(int p){
if(!isRoot(p)){
update(t[p].father);
}
down(p);
}
void rotate(int x){
int y=t[x].father,z=t[y].father;
bool mode=check(x);
t[y].child[mode]=t[x].child[!mode];
t[x].child[!mode]=y;
if(!isRoot(y)){
t[z].child[check(y)]=x;
}
if(t[y].child[mode]){
t[t[y].child[mode]].father=y;
}
t[y].father=x;
t[x].father=z;
up(y);
up(x);
}
void splay(int x){
update(x);
while(!isRoot(x)){
int p=t[x].father;
if(isRoot(p)){
rotate(x);
break;
}
if(check(p)==check(x)){
rotate(p);
rotate(x);
}else{
rotate(x);
rotate(x);
}
}
}
void access(int x){
for(int p=0;x;p=x,x=t[x].father){
splay(x);
t[x].child[1]=p;
up(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
t[x].reverse^=1;
swap(t[x].child[0],t[x].child[1]);
}
int find(int x){
access(x);
splay(x);
down(x);
while(t[x].child[0]){
x=t[x].child[0];
down(x);
}
splay(x);
return x;
}
void split(int u,int v){
makeRoot(u);
access(v);
splay(v);
}
void link(int u,int v){
makeRoot(u);
if(find(v)!=u){
t[u].father=v;
}
}
void cut(int u,int v){
makeRoot(u);
if(find(v)==u&&t[v].father==u&&!t[v].child[0]){
t[v].father=t[u].child[1]=0;
}
}
void add(int u,int v,int x){
split(u,v);
t[v].add=(t[v].add+x)%P;
t[v].value=(t[v].value+x)%P;
t[v].sum=(t[v].sum+1ll*t[v].size*x)%P;
}
void mul(int u,int v,int x){
split(u,v);
t[v].mul=1ll*t[v].mul*x%P;
t[v].add=1ll*t[v].add*x%P;
t[v].value=1ll*t[v].value*x%P;
t[v].sum=1ll*t[v].sum*x%P;
}
int query(int u,int v){
split(u,v);
return t[v].sum;
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
t.build();
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
t.link(u,v);
}
while(m--){
char op;
int u,v,x;
cin>>op>>u>>v;
switch(op){
case '+':
cin>>x;
t.add(u,v,x);
break;
case '-':
t.cut(u,v);
cin>>u>>v;
t.link(u,v);
break;
case '*':
cin>>x;
t.mul(u,v,x);
break;
case '/':
cout<<t.query(u,v)<<'\n';
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## 维护子树信息
> [Luogu P4219 [BJOI2014] 大融合](https://www.luogu.com.cn/problem/P4219)
>
> $n$ 个点 $1\sim n$ 编号，给定 $q$ 次操作：
>
> * `A x y`，加边 $(x,y)$。
> * `Q x y`，询问对于边 $(x,y)$，断开 $(x,y)$ 后子树 $x$ 和子树 $y$ 的子树大小乘积。
>
> 保证任意时刻，$n$ 个点构成一棵森林。
树的形态改变，考虑 LCT。
但是 LCT 并不能很好的维护子树信息，因为虚子节点的信息没有被统计，那么我们就强行加上这一部分的贡献。
本题需要维护**包括虚子树**的子树大小 $\operatorname{size}(x)$。设 $\operatorname{size}_2(x)$ 表示 $x$ 的所有虚子节点子树大小之和。
对应地改一下 `up`：
```cpp
void up(int p){
t[p].size=t[t[p].child[0]].size+1+t[t[p].child[1]].size+t[p].size2;
}
```
除此之外，`rotate` 和 `spaly` 与 $\operatorname{size}_2(x)$ 无关。因为这都是一棵 Splay 内部的操作，不涉及到虚子节点父子关系的变更。
`access` 涉及到了将右子节点直接更换，原来的右子节点便成为了虚子节点。据此更新即可。
```cpp
void access(int x){
for(int p=0;x;p=x,x=t[x].father){
splay(x);
t[x].size2+=t[t[x].child[1]].size-t[p].size;
t[x].child[1]=p;
up(x);
}
}
```
`link` 的操作方式是把 $u$ `makeRoot` 后直接挂在 $v$ 上，成为 $v$ 的虚子节点。
此时就要更新 $v$ 的信息，因此还要先对 $v$ 进行 `makeRoot`，再令 $\operatorname{size}_2(v)\leftarrow\operatorname{size}_2(v)+\operatorname{size}(u)$ 即可。
```cpp
void link(int u,int v){
makeRoot(u);
if(find(v)!=u){
makeRoot(v);
t[u].father=v;
t[v].size2+=t[u].size;
}
}
```
查询时先断边 $(x,y)$，查询后在加边 $(x,y)$ 即可。
- 维护信息可差分。因为将虚边变为实边的时候要排除原来实边的贡献。
- 不可差分的最值，也许可以开
set维护。
LCT 维护子树信息要求
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=1e5;
int n;
struct LCT{
struct node{
int size,size2,father,child[2];
bool reverse;
}t[N+1];
bool check(int p){
return t[t[p].father].child[1]==p;
}
bool isRoot(int p){
return t[t[p].father].child[0]!=p&&t[t[p].father].child[1]!=p;
}
void up(int p){
t[p].size=t[t[p].child[0]].size+1+t[t[p].child[1]].size+t[p].size2;
}
void down(int p){
if(t[p].reverse){
t[t[p].child[0]].reverse^=1;
swap(t[t[p].child[0]].child[0],t[t[p].child[0]].child[1]);
t[t[p].child[1]].reverse^=1;
swap(t[t[p].child[1]].child[0],t[t[p].child[1]].child[1]);
t[p].reverse=false;
}
}
void update(int p){
if(!isRoot(p)){
update(t[p].father);
}
down(p);
}
void rotate(int x){
int y=t[x].father,z=t[y].father;
bool mode=check(x);
t[y].child[mode]=t[x].child[!mode];
t[x].child[!mode]=y;
if(!isRoot(y)){
t[z].child[check(y)]=x;
}
if(t[y].child[mode]){
t[t[y].child[mode]].father=y;
}
t[y].father=x;
t[x].father=z;
up(y);
up(x);
}
void splay(int x){
update(x);
while(!isRoot(x)){
int p=t[x].father;
if(isRoot(p)){
rotate(x);
break;
}
if(check(p)==check(x)){
rotate(p);
rotate(x);
}else{
rotate(x);
rotate(x);
}
}
}
void access(int x){
for(int p=0;x;p=x,x=t[x].father){
splay(x);
t[x].size2+=t[t[x].child[1]].size-t[p].size;
t[x].child[1]=p;
up(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
t[x].reverse^=1;
swap(t[x].child[0],t[x].child[1]);
}
int find(int x){
access(x);
splay(x);
down(x);
while(t[x].child[0]){
x=t[x].child[0];
down(x);
}
splay(x);
return x;
}
void split(int u,int v){
makeRoot(u);
access(v);
splay(v);
}
void link(int u,int v){
makeRoot(u);
if(find(v)!=u){
makeRoot(v);
t[u].father=v;
t[v].size2+=t[u].size;
}
}
void cut(int u,int v){
makeRoot(u);
if(find(v)==u&&t[v].father==u&&!t[v].child[0]){
t[v].father=t[u].child[1]=0;
}
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
while(m--){
char op;
int x,y;
cin>>op>>x>>y;
switch(op){
case 'A':
t.link(x,y);
break;
case 'Q':
t.cut(x,y);
t.makeRoot(x);
t.makeRoot(y);
cout<<1ll*t.t[x].size*t.t[y].size<<'\n';
t.link(x,y);
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## 维护连通性
> [Luogu P2147 [SDOI2008] 洞穴勘测](https://www.luogu.com.cn/problem/P2147)
>
> 给定 $n$ 个点，$m$ 次操作：
>
> * `Connext u v`，加边 $(u,v)$。
> * `Destroy u v`，删边 $(u,v)$。
> * `Query u v`，查询 $u,v$ 是否连通。
>
> 保证任意时刻，原图均为一棵森林。
$u,v$ 所在原树的根节点相同是 $u,v$ 连通的充要条件。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=1e4;
int n;
struct LCT{
struct node{
int father,child[2];
bool reverse;
}t[N+1];
bool check(int p){
return t[t[p].father].child[1]==p;
}
bool isRoot(int p){
return t[t[p].father].child[0]!=p&&t[t[p].father].child[1]!=p;
}
void up(int p){
}
void down(int p){
if(t[p].reverse){
t[t[p].child[0]].reverse^=1;
swap(t[t[p].child[0]].child[0],t[t[p].child[0]].child[1]);
t[t[p].child[1]].reverse^=1;
swap(t[t[p].child[1]].child[0],t[t[p].child[1]].child[1]);
t[p].reverse=false;
}
}
void update(int p){
if(!isRoot(p)){
update(t[p].father);
}
down(p);
}
void rotate(int x){
int y=t[x].father,z=t[y].father;
bool mode=check(x);
t[y].child[mode]=t[x].child[!mode];
t[x].child[!mode]=y;
if(!isRoot(y)){
t[z].child[check(y)]=x;
}
if(t[y].child[mode]){
t[t[y].child[mode]].father=y;
}
t[y].father=x;
t[x].father=z;
up(y);
up(x);
}
void splay(int x){
update(x);
while(!isRoot(x)){
int p=t[x].father;
if(isRoot(p)){
rotate(x);
break;
}
if(check(p)==check(x)){
rotate(p);
rotate(x);
}else{
rotate(x);
rotate(x);
}
}
}
void access(int x){
for(int p=0;x;p=x,x=t[x].father){
splay(x);
t[x].child[1]=p;
up(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
t[x].reverse^=1;
swap(t[x].child[0],t[x].child[1]);
}
int find(int x){
access(x);
splay(x);
down(x);
while(t[x].child[0]){
x=t[x].child[0];
down(x);
}
splay(x);
return x;
}
void split(int u,int v){
makeRoot(u);
access(v);
splay(v);
}
void link(int u,int v){
makeRoot(u);
if(find(v)!=u){
t[u].father=v;
}
}
void cut(int u,int v){
makeRoot(u);
if(find(v)==u&&t[v].father==u&&!t[v].child[0]){
t[v].father=t[u].child[1]=0;
}
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
while(m--){
string op;
int x,y;
cin>>op>>x>>y;
switch(op[0]){
case 'C':
t.link(x,y);
break;
case 'D':
t.cut(x,y);
break;
case 'Q':
cout<<(t.find(x)==t.find(y)?"Yes":"No")<<'\n';
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
