动态树（Link Cut Tree）
简介
Link/Cut Tree 是一种数据结构，我们用它来解决动态树问题。
Link/Cut Tree 又称 \(Link-Cut Tree\)，简称 \(LCT\)，但它不叫动态树，动态树是指一类问题。
Splay Tree 是 \(LCT\) 的基础，但是 \(LCT\) 用的 \(Splay Tree\) 和普通的 \(Splay\) 在细节处不太一样（进行了一些扩展）。
这是一个和 \(Splay\) 一样只需要写几 \((yi)\) 个 \((dui)\) 核心函数就能实现一切的数据结构。
基本操作
struct tree{
int f,ch[2],val,sum,lz;
}t[N];
一般数据结构函数
il void PushUp(ri int x){
t[x].sum=t[t[x].ch[0]].sum^t[t[x].ch[1]].sum^t[x].val;
}
il void PushDown(ri int x){
if(t[x].lz){
if(t[x].ch[0]) Reverse(t[x].ch[0]);
if(t[x].ch[1]) Reverse(t[x].ch[1]);
t[x].lz=0;
}
}
\(Splay\) 系函数
#define Son(x) (x==t[t[x].f].ch[1])
il void Rotate(ri int x){
ri int y=t[x].f,z=t[y].f,k=Son(x);
if(NotRoot(y)) t[z].ch[Son(y)]=x;
if(t[x].ch[!k]) t[t[x].ch[!k]].f=y;
t[y].ch[k]=t[x].ch[!k],t[x].ch[!k]=y;
t[y].f=x,t[x].f=z,PushUp(y);
}
il void Splay(ri int x){
Update(x);
for(ri int fa;fa=t[x].f,NotRoot(x);Rotate(x)){
if(NotRoot(fa)) Rotate(Son(fa)^Son(x)?x:fa);
}
PushUp(x);
}
新操作
Access(x)把从根到 \(x\) 的所有点放在一条实链里，使根到 \(x\) 成为一条实路径，并且在同一棵 \(Splay\) 里。只有此操作是必须实现的，其他操作视题目而实现。IsRoot(x)/NotRoot(x)判断 \(x\) 是否是所在树的根。Reverse(x)交换 \(x\) 的子树。Update(x)在 \(Access\) 操作之后，递归地从上到下 \(PushDown\) 更新信息。MakeRoot(x)使 \(x\) 点成为其所在树的根。Link(x, y)在 \(x, y\) 两点间连一条边。Cut(x, y)把 \(x, y\) 两点间边删掉。FindRoot(x)找到 \(x\) 所在树的根节点编号。Fix(x, v)修改 \(x\) 的点权为 \(v\)。Split(x, y)提取出 \(x, y\) 间的路径，方便做区间操作。
\(Access\)
il void Access(ri int x){
for(ri int y=0;x;x=t[y=x].f){
Splay(x),t[x].ch[1]=y,PushUp(x);
}
}
\(IsRoot/NotRoot\)
#define IsRoot(x) ((x^t[t[x].f].ch[0])&&(x^t[t[x].f].ch[1]))
由于总是用到!IsRoot，所以直接写NotRoot了
#define NotRoot(x) (t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x)
\(Reverse\)
il void Reverse(ri int x){
swap(t[x].ch[0],t[x].ch[1]);
t[x].lz^=1;
}
\(Update\)
il void Update(ri int x){
if(NotRoot(x)) Update(t[x].f);
PushDown(x);
}
\(MakeRoot\)
il void MakeRoot(ri int x){
Access(x),Splay(x),Reverse(x);
}
\(Link\)
il void Link(ri int x,ri int y){
MakeRoot(x);
if(FindRoot(y)!=x)t[x].f=y;
}
\(Cut\)
il void Cut(ri int x,ri int y){
MakeRoot(x);
if(FindRoot(y)==x&&t[y].f==x&&!t[y].ch[0]){
t[y].f=t[x].ch[1]=0,PushUp(x);
}
}
\(FindRoot\)
il int FindRoot(ri int x){
Access(x),Splay(x);
while(t[x].ch[0]) PushDown(x),x=t[x].ch[0];
Splay(x); return x;
}
\(Fix\)
il void Fix(int x,int y){
Splay(x),t[x].val=y;
}
\(Split\)
il void Split(ri int x,ri int y){
MakeRoot(x),Access(y),Splay(y);
}
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c==45),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10|48),void();
}
} using namespace Q;
cs int N=1e5+5;
namespace Link_Cut_Tree{
#define NotRoot(x) (t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x)
#define Son(x) (x==t[t[x].f].ch[1])
struct tree{
int f,ch[2],val,sum,lz;
}t[N];
il void Reverse(ri int x){
swap(t[x].ch[0],t[x].ch[1]);
t[x].lz^=1;
}
il void PushDown(ri int x){
if(t[x].lz){
if(t[x].ch[0]) Reverse(t[x].ch[0]);
if(t[x].ch[1]) Reverse(t[x].ch[1]);
t[x].lz=0;
}
}
il void Update(ri int x){
if(NotRoot(x)) Update(t[x].f);
PushDown(x);
}
il void PushUp(ri int x){
t[x].sum=t[t[x].ch[0]].sum^t[t[x].ch[1]].sum^t[x].val;
}
il void Rotate(ri int x){
ri int y=t[x].f,z=t[y].f,k=Son(x);
if(NotRoot(y)) t[z].ch[Son(y)]=x;
if(t[x].ch[!k]) t[t[x].ch[!k]].f=y;
t[y].ch[k]=t[x].ch[!k],t[x].ch[!k]=y;
t[y].f=x,t[x].f=z,PushUp(y);
}
il void Splay(ri int x){
Update(x);
for(ri int fa;fa=t[x].f,NotRoot(x);Rotate(x)){
if(NotRoot(fa)) Rotate(Son(fa)^Son(x)?x:fa);
}
PushUp(x);
}
il void Access(ri int x){
for(ri int y=0;x;x=t[y=x].f){
Splay(x),t[x].ch[1]=y,PushUp(x);
}
}
il void MakeRoot(ri int x){
Access(x),Splay(x),Reverse(x);
}
il int FindRoot(ri int x){
Access(x),Splay(x);
while(t[x].ch[0]) PushDown(x),x=t[x].ch[0];
Splay(x); return x;
}
il void Split(ri int x,ri int y){
MakeRoot(x),Access(y),Splay(y);
}
il void Link(ri int x,ri int y){
MakeRoot(x);
if(FindRoot(y)!=x)t[x].f=y;
}
il void Cut(ri int x,ri int y){
MakeRoot(x);
if(FindRoot(y)==x&&t[y].f==x&&!t[y].ch[0]){
t[y].f=t[x].ch[1]=0,PushUp(x);
}
}
il void Fix(int x,int y){
Splay(x),t[x].val=y;
}
} using namespace Link_Cut_Tree;
int main(){
ri int n=rd(),m=rd();
for(ri int i=1;i<=n;++i)t[i].val=rd();
for(ri int i=1,op,x,y;i<=m;++i){
op=rd(),x=rd(),y=rd();
switch(op){
case 0:Split(x,y),wt(t[y].sum),putchar(10);break;
case 1:Link(x,y);break;
case 2:Cut(x,y);break;
case 3:Fix(x,y);break;
}
}
return 0;
}