P3690 【模板】Link Cut Tree (动态树)

时间:2022-11-04 21:35:32

P3690 【模板】Link Cut Tree (动态树)

认父不认子的lct

注意:不 要 把 $fa[x]$和$nrt(x)$ 混 在 一 起 !

#include<cstdio>
void swap(int &a,int &b){a^=b^=a^=b;}
#define N 300005
int n,m,s[N],v[N],ch[][N],fa[N],rev[N];
#define lc ch[0][x]
#define rc ch[1][x]
bool nrt(int x){return ch[][fa[x]]==x||ch[][fa[x]]==x;}
void up(int x){s[x]=s[lc]^v[x]^s[rc];}
void Rev(int x){swap(lc,rc);rev[x]^=;}
void down(int x){if(rev[x])Rev(lc),Rev(rc),rev[x]=;}
void fadown(int x){if(nrt(x))fadown(fa[x]); down(x);}
void turn(int x){
int y=fa[x],z=fa[y],l=(ch[][y]==x),r=l^;
if(nrt(y)) ch[ch[][z]==y][z]=x;
fa[ch[r][x]]=y; fa[x]=z; fa[y]=x;
ch[l][y]=ch[r][x]; ch[r][x]=y;
up(y); up(x);
}
void splay(int x){
fadown(x);
for(;nrt(x);turn(x)){
int y=fa[x],z=fa[y];
if(nrt(y)) turn((ch[][y]==x)^(ch[][z]==y)?x:y);
}
}
void access(int x){for(int y=;x;y=x,x=fa[x])splay(x),rc=y,up(x);}//构造一棵splay,把当前树根与x用重边连起来
void makert(int x){access(x);splay(x);Rev(x);}//总树根改为x
int find(int x){//找x所在树的树根
access(x);splay(x);down(x);
while(lc) x=lc,down(x);
splay(x); return x;
}
void link(int x,int y){makert(x); if(find(y)!=x)fa[x]=y;}
void cut(int x,int y){
makert(x);
if(find(y)==x&&fa[y]==x&&!ch[][y]) rc=fa[y]=,up(x);
}
void split(int x,int y){makert(x);access(y);splay(y);}//拉出一条x-y的路径成为一个根为y的splay
int main(){
scanf("%d%d",&n,&m); int q1,q2,q3;
for(int i=;i<=n;++i) scanf("%d",&v[i]);
while(m--){
scanf("%d%d%d",&q1,&q2,&q3);
if(q1==) split(q2,q3),printf("%d\n",s[q3]);
else if(q1==) link(q2,q3);
else if(q1==) cut(q2,q3);
else splay(q2),v[q2]=q3;
}return ;
}