动态树（Link Cut Tree）
彭俊皓123
·
·
个人记录
一、算法简介
主要思想是建立一座含有多棵 $Splay$ 的森林以替代原来的树结构，
并通过 **实链剖分** 对树进行动态剖分实现的。
其复杂度是 $O(qlogn)$ 级别的。
# 二、实现原理
对于两棵点集互不相交的树，其结构只和其相连的边（最多一条）有关；
而对于同一棵树，可以将其按照其遍历顺序进行改造，
在保证其遍历顺序不变的前提下实现树结构的动态转换。
## 辅助树：
在进行操作之前，先建立一棵辅助树以改造原树。
为了保证原树的结构唯一确定，辅助树需要满足 **中序遍历** （左中右）的结果与原树相同。
换而言之，对于辅助树中的一个节点，
**其左子节点在原树中比其先遍历到，而右子节点比其后遍历到。**
在满足这个性质的前提下建树，则可以在遍历整棵树时直接通过 $dfs$ 进行中序遍历。
## 实链剖分：
如同 [树链剖分](https://www.luogu.com.cn/blog/pengjunhao123/tree-line-pow-divide) 一样，一个点选取所有子节点中的一条边，使其成为 **实链**，
相对应地，其他未成为实链的边称之为 **虚链**。
被父节点以实链链接的节点称为 **实节点**，反之为 **虚结点**。
性质：一个点可以 **通过实链** 被父节点查询到，
而虚链具有单向性（**父节点无法查询子节点**，而子节点可以查询父节点）。
这条性质使得多棵 $Splay$ 之间可以互相区分开来。
**由于LCT能维护的东西众多，对具体操作的实现放入下节。**
# 三、具体实现
温馨提示：请确保您在阅读以下内容前已经学习过了 [Splay](https://oi-wiki.org/ds/splay/)。
## 0.check/isroot(判断父子节点关系）
$check$ 函数用于查询节点在父节点的左或右节点，
而 $isroot$ 函数用于查询节点 **是否是所在 $Splay$ 的根**。
可以通过虚节点与父节点关系的 **单向性** 得到。
代码如下：
```cpp
bool check(int k)
{
return rs(fa(k))==k;
}
bool isroot(int k)
{
return ls(fa(k))!=k&&rs(fa(k))!=k;
}
```
注意：对 $LCT$ 的根与对 $Splay$ 的根进行查询是不同的操作！
## 1.pushup（上传节点信息）
根据题目的要求，可能需要维护虚子树的信息。
以 [P3690 【模板】动态树（LCT）](https://www.luogu.com.cn/problem/P3690)
与
[Jamie and Tree](https://www.luogu.com.cn/problem/CF916E)
两题分别为例：
对于前者，只需要维护路径上异或和，进行实链剖分后即可完成:
```cpp
void pushup(int k)
{
sum[k]=sum[son[k][0]]^sum[son[k][1]]^val[k];
}
```
而对于后者，不难发现其子树上必然会有虚链未被统计到，于是也要维护虚链信息：
（包括但不限于虚子树大小、实子树大小、虚节点答案和等信息）
```cpp
void pushup(int k)
{
siz(k)=siz(ls(k))+siz(rs(k))+isiz(k)+1;
tsiz(k)=tsiz(ls(k))+tsiz(rs(k))+1;
sumsiz(k)=sumsiz(ls(k))+sumsiz(rs(k))+isiz(k);
sum(k)=sum(ls(k))+sum(rs(k))+isum(k)+val(k)+isiz(k)*det(k);
}
```
## 2.pushdown（下传翻转标记）
在 $LCT$ 旋转树的过程中，会出现左右子节点反转的情况，需要打上标记后旋转回去。
同时，根据题目需要，也可以维护一些操作的标记。
仍以
[Jamie and Tree](https://www.luogu.com.cn/problem/CF916E)
为例，本题需要维护子树加，所以需要对虚实子树分别打上标记后下传。
```cpp
void pushdown(int k)
{
if(revtag(k))rev(ls(k)),rev(rs(k)),revtag(k)=0;
add(ls(k),tag(k)),add(rs(k),tag(k)),tag(k)=0;
iadd(ls(k),itag(k)),iadd(rs(k),itag(k)),itag(k)=0;
}
```
在以上代码中，通过函数 $add(k)$ 与 $iadd(k)$ 分别维护了对实节点和虚结点的标记。
## 3.rotate（Splay的旋转操作）
基本上与 $Splay$ 中操作相同，但需要判断父节点是否为所在 $Splay$ 的根。
若父节点为根，则祖父节点与其不在同一棵 $Splay$ 中，
于是只需要判断祖父节点的左右儿子是否存在父节点即可。
为了维护实链剖分性质，
若父节点为根，则不需要从祖父节点向父节点确定子节点关系了。
代码如下：
```cpp
void rotate_(int k)
{
int fath=fa(k),gath=fa(fath);
int inv=check(k);
if(!isroot(fath))node[gath].son[check(fath)]=k;
//上文所讨论的判断在此处
node[fath].son[inv]=node[k].son[inv^1];
fa(node[k].son[inv^1])=fath;
node[k].son[inv^1]=fath;
fa(fath)=k;
fa(k)=gath;
pushup(fath);pushup(k);
}
```
## 4.splay（将节点转到Splay的根）
与普通 $Splay$ 不同的是，
在开始旋转之前，需要先将节点到 $Splay$ 的根路径所有的 **翻转标记** 进行更新。
记得将判断条件改为判断是否处于 $Splay$ 根即可。
代码如下：
```cpp
void splay(int k)
{
update(k);
while(!isroot(k))
{
if(!isroot(fa(k)))rotate_(check(k)^(check(fa(k)))?k:fa(k));
rotate_(k);
}
}
```
## 5.access（实链剖分）
为了使得某个节点到根节点的路径为实路径，需要对多棵 $Splay$ 的结构进行改变。
由于虚实链的定义只对于所属 $Splay$ 不同的节点生效，只需要修改链的起始端点位置即可。
具体而言，需要将父节点旋转到其所在子树的根，并使其与自身建立双向边，
接着对父节点进行同样的操作即可。
建立双向边的过程实则为确定 **父节点的右节点为此节点** 即可，
这点可以由辅助树的 **中序遍历** 性质得到。
代码如下：
```cpp
int access(int k)
{
int last=0;
while(k)
{
splay(k);
rs(k)=last,pushup(k);
last=k,k=fa(k);
}
return last;
}
```
根据题目要求的不同，可以对 $access(x)$ 进行一定的改造，
如在重连实边的同时重新统计虚实子树的信息等。
### 以上操作为LCT的基本操作，接下来的操作基本上均为调用以上操作得到。
## 6.makeroot（将某个节点转到LCT的根）
首先需要对节点进行实链剖分，然后将其转到根即可。
由于这个过程中 $LCT$ 的根节点的左右子节点会发生翻转，需要打上翻转标记。
代码如下：
```cpp
void makeroot(int k)
{
access(k);
splay(k);
swap(ls(k),rs(k));revtag(k)^=1;
}
```
**注意！如果需要查询某个点作为根时候的信息，而不产生后效性，请不要对子树进行翻转，而是直接 $access(x)$ 后 $splay(x)$。**
## 7.findroot(查询某棵辅助树所对应原树的根）
由辅助树建树性质可得，只需要查整棵 $Splay$ 最左边的节点即可。
代码如下：
```cpp
int findroot(int k)
{
access(k);splay(k);
while(son[k][0])k=son[k][0];
return k;
}
```
## 8.split（提取出一段路径）
将一端的节点旋转到 $LCT$ 的根，
再对另一端的节点进行实链剖分后旋转到根即可。
代码如下：
```cpp
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
```
>>这里与 $makeroot$ 部分的注意事项原理是相同的：在对 $x$ 进行实际旋转后，对 $y$ 的旋转实际上并没有进行，而只是为了便于查询路径才将其旋转，于是 **不需要** 翻转左右子节点。
## 9.link(在两个节点之间建边）
连接两个节点，意味着合并了其所在的两棵 $Splay$。
于是直接将一端转到 $LCT$ 的根，并与另一端相连即可。
代码如下：
```cpp
void link(int x,int y)
{
if(findroot(x)==findroot(y))return;
makeroot(x);
fa(x)=y;
}
```
## 10.cut(断开两个节点之间的边）
先将两个节点之间的路径用 $split$ 函数提取出来，
提取出来后由辅助树的中序遍历性质可知，
**其中一个点一定是另一个点的右子节点。**
于是可以直接清零。
代码如下：
```cpp
void cut(int x,int y)
{
if(findroot(x)!=findroot(y))return;
split(x,y);
if(ls(y)==x&&!rs(x))fa(x)=ls(y)=0;
}
```
剩下的还有对子树进行修改等操作，等来兴趣了再补充。
# 四、复杂度证明
$Splay$ 该怎么证这个就该怎么证。
不会，有机会了再写。
# 五、其他
其实 $LCT$ 的灵活性很高，等写到有意思的题了再在这里贴几个。
# 六、代码
[P3690 【模板】动态树（LCT）](https://www.luogu.com.cn/problem/P3690)
模板。
```cpp
#include<iostream>
using namespace std;
const int MAXN=100005;
int a,b,c;
int num[MAXN];
inline int read()
{
char x=getchar();int t=0;
while(!isdigit(x))x=getchar();
while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
return t;
}
struct LCT
{
struct nodes
{
int fa,siz,son[2];
int val,sum,tag;
#define fa(k) node[k].fa
#define siz(k) node[k].siz
#define ls(k) node[k].son[0]
#define rs(k) node[k].son[1]
#define val(k) node[k].val
#define sum(k) node[k].sum
#define tag(k) node[k].tag
}node[MAXN];
bool check(int k){return rs(fa(k))==k;}
bool isroot(int k){return ls(fa(k))!=k&&rs(fa(k))!=k;}
void pushup(int k){sum(k)=sum(ls(k))^sum(rs(k))^val(k);}
void pushdown(int k){if(tag(k))swap(ls(k),rs(k)),tag(ls(k))^=1,tag(rs(k))^=1,tag(k)=0;}
void update(int k){if(!isroot(k))update(fa(k));pushdown(k);}
void rotate_(int k)
{
int fath=fa(k),gath=fa(fath);
int inv=check(k);
if(!isroot(fath))node[gath].son[check(fath)]=k;
fa(k)=gath,fa(fath)=k;
fa(node[k].son[inv^1])=fath;
node[fath].son[inv]=node[k].son[inv^1];
node[k].son[inv^1]=fath;
pushup(fath);pushup(k);
}
void splay(int k)
{
update(k);
while(!isroot(k))
{
if(!isroot(fa(k)))rotate_(check(k)^(check(fa(k)))?k:fa(k));
rotate_(k);
}
}
int access(int k)
{
int last=0;
while(k)
{
splay(k);
rs(k)=last,pushup(k);
last=k,k=fa(k);
}
return last;
}
void makeroot(int k){access(k);splay(k);tag(k)^=1;}
int findroot(int k){access(k);splay(k);while(ls(k))k=ls(k);return k;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){if(findroot(x)==findroot(y))return;makeroot(x);fa(x)=y;}
void cut(int x,int y){if(findroot(x)!=findroot(y))return;split(x,y);if(ls(y)==x&&!rs(x))fa(x)=ls(y)=0;}
}lct;
int main()
{
a=read();b=read();
for(int i=1;i<=a;++i)lct.val(i)=read();
while(b--)
{
int opt=read(),x=read(),y=read();
switch(opt){
case 0:lct.split(x,y);printf("%d\n",lct.sum(y));break;
case 1:lct.link(x,y);break;
case 2:lct.cut(x,y);break;
case 3:
lct.access(x);lct.splay(x);
lct.val(x)=y;
lct.pushup(x);
break;
}
}
}
```
[P3203 [HNOI2010] 弹飞绵羊](https://www.luogu.com.cn/problem/P3203)
这题将每个节点与下一个节点相连后是一棵树，
但由于题目给出了修改的条件，考虑动态树处理。
操作一：查询 $i$ 到 $n+1$ 号点的路径长度；
操作二：将 $i$ 与其原来父节点断开后连新边即可。
注意：每次的查询操作虽然要把 $n+1$ 号点旋转到根进行查询，
但并不需要调用 $makeroot$ 函数（因为并没有真正旋转）
```cpp
#include<iostream>
#define ll long long
using namespace std;
const int MAXN=200005;
int a,b,c;
int num[MAXN];
struct LCT
{
struct nodes
{
int fa;
int revtag;
int son[2],siz;
nodes():fa(0),revtag(false),siz(0){son[0]=son[1]=0;}
void clear()
{
fa=revtag=siz=0;
son[0]=son[1]=0;
}
#define fa(k) node[k].fa
#define ls(k) node[k].son[0]
#define rs(k) node[k].son[1]
#define revtag(k) node[k].revtag
#define siz(k) node[k].siz
}node[MAXN];
void pushup(int k){siz(k)=siz(ls(k))+siz(rs(k))+1;}
void rev(int k){swap(ls(k),rs(k));revtag(k)^=1;}
void pushdown(int k){if(revtag(k))rev(ls(k)),rev(rs(k)),revtag(k)=0;}
bool check(int k){return rs(fa(k))==k;}
bool isroot(int k){return ls(fa(k))!=k&&rs(fa(k))!=k;}
void update(int k){if(!isroot(k))update(fa(k));pushdown(k);}
void rotate_(int k)
{
int fath=fa(k),gath=fa(fath);
int inv=check(k);
if(!isroot(fath))node[gath].son[check(fath)]=k;
node[fath].son[inv]=node[k].son[inv^1];
fa(node[k].son[inv^1])=fath;
node[k].son[inv^1]=fath;
fa(fath)=k;
fa(k)=gath;
pushup(fath);pushup(k);
}
void splay(int k)
{
update(k);
while(!isroot(k))
{
if(!isroot(fa(k)))rotate_(check(k)^check(fa(k))?k:fa(k));
rotate_(k);
}
}//
int access(int k)
{
int last=0;
while(k)
{
splay(k);
rs(k)=last,pushup(k);
last=k,k=fa(k);
}
return last;
}
void makeroot(int k){access(k);splay(k);swap(ls(k),rs(k));revtag(k)^=1;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);makeroot(y);access(y);fa(x)=y,rs(y)=x;pushup(y);}
void cut(int x,int y){split(x,y);if(ls(y)==x&&!rs(x))fa(x)=ls(y)=0;}
}lct;
inline int read()
{
char x=getchar();int t=0;
while(!isdigit(x))x=getchar();
while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
return t;
}
int main()
{
a=read();
for(int i=1;i<=a;++i)
{
int x=read();
num[i]=min(i+x,a+1);
lct.link(i,num[i]);
}
b=read();
while(b--)
{
int opt=read(),x=read()+1,y;
switch(opt){
case 1:
lct.split(x,a+1);
printf("%d\n",lct.siz(lct.ls(a+1)));
break;
case 2:
y=read();
lct.cut(x,num[x]);
num[x]=min(x+y,a+1);
lct.link(x,num[x]);
break;
}
}
}
```
[P3950 部落冲突](https://www.luogu.com.cn/problem/P3950)
比模板还板，只需要查询根节点是否相同就行了。
```cpp
#include<iostream>
#define ll long long
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define f first
#define s second
using namespace std;
const int MAXN=300005;
int a,b,c,tot=0;
pii war[MAXN];
struct LCT
{
struct nodes
{
int fa;
int revtag;
int son[2],siz;
nodes():fa(0),revtag(false),siz(0){son[0]=son[1]=0;}
void clear()
{
fa=revtag=siz=0;
son[0]=son[1]=0;
}
#define fa(k) node[k].fa
#define ls(k) node[k].son[0]
#define rs(k) node[k].son[1]
#define revtag(k) node[k].revtag
#define siz(k) node[k].siz
}node[MAXN];
void pushup(int k)
{
siz(k)=siz(ls(k))+siz(rs(k))+1;
}
void rev(int k){swap(ls(k),rs(k));revtag(k)^=1;}
void pushdown(int k)
{
if(revtag(k))rev(ls(k)),rev(rs(k)),revtag(k)=0;
}
bool check(int k){return rs(fa(k))==k;}
bool isroot(int k){return ls(fa(k))!=k&&rs(fa(k))!=k;}
void update(int k){if(!isroot(k))update(fa(k));pushdown(k);}
void rotate_(int k)
{
int fath=fa(k),gath=fa(fath);
int inv=check(k);
if(!isroot(fath))node[gath].son[check(fath)]=k;
node[fath].son[inv]=node[k].son[inv^1];
fa(node[k].son[inv^1])=fath;
node[k].son[inv^1]=fath;
fa(fath)=k;
fa(k)=gath;
pushup(fath);pushup(k);
}
void splay(int k)
{
update(k);
while(!isroot(k))
{
if(!isroot(fa(k)))rotate_(check(k)^check(fa(k))?k:fa(k));
rotate_(k);
}
}
int access(int k)
{
int last=0;
while(k)
{
splay(k);
rs(k)=last,pushup(k);
last=k,k=fa(k);
}
return last;
}
void makeroot(int k){access(k);splay(k);swap(ls(k),rs(k));revtag(k)^=1;}
int findroot(int k){access(k);splay(k);while(ls(k))k=ls(k);return k;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);makeroot(y);access(y);fa(x)=y,rs(y)=x;pushup(y);}
void cut(int x,int y){split(x,y);if(ls(y)==x&&!rs(x))fa(x)=ls(y)=0;}
}lct;
inline int read()
{
char x=getchar();int t=0;
while(!isdigit(x))x=getchar();
while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
return t;
}
int main()
{
a=read();b=read();
for(int i=1;i<a;++i)
{
int x=read(),y=read();
lct.link(x,y);
}
while(b--)
{
char opt;cin>>opt;
int x=read(),y;
switch(opt){
case 'Q':
y=read();
puts(lct.findroot(x)==lct.findroot(y)?"Yes":"No");
break;
case 'C':
y=read();
lct.cut(x,y);
war[++tot]=mp(x,y);
break;
case 'U':
y=war[x].f,x=war[x].s;
lct.link(x,y);
break;
}
}
}
```