动态树与LCT
LCT：Link Cut Tree
可以用来解决动态地连接和删除
结合树链剖分（实链剖分）和Splay树
“原树实链从上到下，对应Splay树从左到右”
把原树转化到辅助树上操作
而辅助树由若干个Splay树用虚边相连得来
P3690 【模板】动态树（Link Cut Tree）
#include <bits/stdc++.h>
using namespace std;
#define fa(x) tr[x].fa
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
#define notroot(x) ls(fa(x))==x||rs(fa(x))==x //判断x不是某个Splay树的根
//原树实链从上到下，对应splay树从左到右
const int maxn=3e5+10;
int n,m;
struct node{
int s[2],fa,val,sum,tag;//tag是翻转懒标记
}tr[maxn];
//pushup更新x的值
void pushup(int x){
tr[x].sum=tr[x].val^tr[ls(x)].sum^tr[rs(x)].sum;
}
//pushdown下放懒标记
void pushdown(int x){
if(tr[x].tag){
swap(ls(x),rs(x));
tr[ls(x)].tag^=1;
tr[rs(x)].tag^=1;
tr[x].tag=0;
}
}
//rotate旋转Splay树
void rotate(int x){
int y=fa(x),z=fa(y);
int k= rs(y)==x;
if(notroot(y))//连x->z必须在最前面，否则后面y改变了就会影响虚边
tr[z].s[rs(z)==y]=x;
fa(x)=z;
tr[y].s[k]=tr[x].s[k^1];
fa(tr[x].s[k^1])=y;
tr[x].s[k^1]=y;
fa(y)=x;
pushup(y);pushup(x);
}
//pushall在每一次splay时都要更新要改变的点懒标记
void pushall(int x){
if(notroot(x)) pushall(fa(x));
pushdown(x);
}
//splay把x旋转到Splay树的根
void splay(int x){
pushall(x);
while(notroot(x)){
int y=fa(x),z=fa(y);
if(notroot(y))
(ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);//折转底，直转中
rotate(x);
}
}
//access从x打一条通路到根
void access(int x){
for(int y=0;x;){
splay(x);
rs(x)=y;//把有用的虚边变成实边，把没用的实边变成虚边
pushup(x);//更新x
y=x,x=fa(x);
}
}
//makeroot换根
void makeroot(int x){
access(x);
splay(x);//此时x在原树的最下面
tr[x].tag^=1;//让x作为原树中的根，对应splay树上左右翻转
}
//split求x->y路径上异或和
void split(int x,int y){
makeroot(x);
access(y);
splay(y);//此时y为根
}
//output输出
void output(int x,int y){
split(x,y);
printf("%d\n",tr[y].sum);
}
//findroot找到x在原树上的根
int findroot(int x){
access(x);
splay(x);//此时x的根在这条链最下面
while(ls(x))
pushdown(x),x=ls(x);
splay(x);//防止卡链
return x;
}
//link连边
void link(int x,int y){
makeroot(x);
if(findroot(y)!=x) fa(x)=y;//不能颠倒，因为x是一个splay的根而y不一定
}
//cut断边
void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&fa(y)==x&&!ls(y))//y要是一个splay的根
fa(y)=0,pushup(x);
}
//change修改
void change(int x,int val){
splay(x);
tr[x].val=val;
pushup(x);
}
int main(){
/*2023.4.15 hewanying P3690 【模板】动态树（Link Cut Tree） LCT*/
scanf("%d%d",&n,&m);
int op,x,y;
for(int i=1;i<=n;i++) scanf("%d",&tr[i].val);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&op,&x,&y);
if(op==0) output(x,y);
if(op==1) link(x,y);
if(op==2) cut(x,y);
if(op==3) change(x,y);
}
return 0;
}
时间复杂度
和Splay一样 \(O(m \log_2 n)\)