浅谈LCT（动态树）
一、算法简介
LCT(link−cut−tree) 是一种可以维护树上动态关系的数据结构。
主要思想是建立一座含有多棵 Splay 的森林以替代原来的树结构，
并通过 实链剖分 对树进行动态剖分实现的。
其复杂度是 O(qlogn) 级别的。
二、实现原理
对于两棵点集互不相交的树，其结构只和其相连的边（最多一条）有关；
而对于同一棵树，可以将其按照其遍历顺序进行改造，
在保证其遍历顺序不变的前提下实现树结构的动态转换。
辅助树：
在进行操作之前，先建立一棵辅助树以改造原树。
为了保证原树的结构唯一确定，辅助树需要满足 中序遍历 （左中右）的结果与原树相同。
换而言之，对于辅助树中的一个节点，
其左子节点在原树中比其先遍历到，而右子节点比其后遍历到。
在满足这个性质的前提下建树，则可以在遍历整棵树时直接通过 dfs 进行中序遍历。
实链剖分：
如同 树链剖分 一样，一个点选取所有子节点中的一条边，使其成为 实链，
相对应地，其他未成为实链的边称之为 虚链。
被父节点以实链链接的节点称为 实节点，反之为 虚结点。
性质：一个点可以 通过实链 被父节点查询到，
而虚链具有单向性（父节点无法查询子节点，而子节点可以查询父节点）。
这条性质使得多棵 Splay 之间可以互相区分开来。
由于LCT能维护的东西众多，对具体操作的实现放入下节。
三、具体实现
温馨提示：请确保您在阅读以下内容前已经学习过了 Splay。
0.check/isroot(判断父子节点关系）
check 函数用于查询节点在父节点的左或右节点，
而 isroot 函数用于查询节点 是否是所在 Splay 的根。
可以通过虚节点与父节点关系的 单向性 得到。
代码如下：
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） 与 Jamie and Tree 两题分别为例：
对于前者，只需要维护路径上异或和，进行实链剖分后即可完成:
void pushup(int k)
{
sum[k]=sum[son[k][0]]^sum[son[k][1]]^val[k];
}
而对于后者，不难发现其子树上必然会有虚链未被统计到，于是也要维护虚链信息： （包括但不限于虚子树大小、实子树大小、虚节点答案和等信息）
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 为例，本题需要维护子树加，所以需要对虚实子树分别打上标记后下传。
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 中，
于是只需要判断祖父节点的左右儿子是否存在父节点即可。
为了维护实链剖分性质，
若父节点为根，则不需要从祖父节点向父节点确定子节点关系了。
代码如下：
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 根即可。
代码如下：
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 不同的节点生效，只需要修改链的起始端点位置即可。
具体而言，需要将父节点旋转到其所在子树的根，并使其与自身建立双向边，
接着对父节点进行同样的操作即可。
建立双向边的过程实则为确定 父节点的右节点为此节点 即可，
这点可以由辅助树的 中序遍历 性质得到。
代码如下：
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 的根节点的左右子节点会发生翻转，需要打上翻转标记。
代码如下：
void makeroot(int k)
{
access(k);
splay(k);
swap(ls(k),rs(k));revtag(k)^=1;
}
注意！如果需要查询某个点作为根时候的信息，而不产生后效性，请不要对子树进行翻转，而是直接 access(x) 后 splay(x)。
7.findroot(查询某棵辅助树所对应原树的根）
由辅助树建树性质可得，只需要查整棵 Splay 最左边的节点即可。
代码如下：
int findroot(int k)
{
access(k);splay(k);
while(son[k][0])k=son[k][0];
return k;
}
8.split（提取出一段路径）
将一端的节点旋转到 LCT 的根，
再对另一端的节点进行实链剖分后旋转到根即可。
代码如下：
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
这里与 makeroot 部分的注意事项原理是相同的：在对 x 进行实际旋转后，对 y 的旋转实际上并没有进行，而只是为了便于查询路径才将其旋转，于是 不需要 翻转左右子节点。
9.link(在两个节点之间建边）
连接两个节点，意味着合并了其所在的两棵 Splay。
于是直接将一端转到 LCT 的根，并与另一端相连即可。
代码如下：
void link(int x,int y)
{
if(findroot(x)==findroot(y))return;
makeroot(x);
fa(x)=y;
}
10.cut(断开两个节点之间的边）
先将两个节点之间的路径用 split 函数提取出来，
提取出来后由辅助树的中序遍历性质可知，
其中一个点一定是另一个点的右子节点。
于是可以直接清零。
代码如下：
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 的灵活性很高，等写到有意思的题了再在这里贴几个。
六、代码
模板。
#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;
}
}
}
这题将每个节点与下一个节点相连后是一棵树，
但由于题目给出了修改的条件，考虑动态树处理。
操作一：查询 i 到 n+1 号点的路径长度；
操作二：将 i 与其原来父节点断开后连新边即可。
注意：每次的查询操作虽然要把 n+1 号点旋转到根进行查询，
但并不需要调用 makeroot 函数（因为并没有真正旋转）
#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;
}
}
}
比模板还板，只需要查询根节点是否相同就行了。
#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;
}
}
}
