[算法模版]Link-Cut-Tree

博主懶本博客只對現有博客進行補充，先直接放隔壁鏈接。

FlashHu-LCT總結

Menci-LCT學習筆記

make-root操作

make-root操作用于把任何一個點反轉到當前樹的根節點。

做法是先把要進行操作的節點x進行access，將root和x進行連通。然后進行splay(x)操作，把x變成splay的根。（請注意，這時候x在主樹的深度仍然沒有改變）。

隨后將x的子樹全部進行反轉操作。也就是改變了這個splay的深度。雖然splay和splay之間的連接需要依賴深度關系（一棵splay的虛邊連接向當前splay中序遍歷序列的首位在原樹上的父親）。但是因為相對關系不變，所以不影響。

看圖（圖來自 動態仙人掌系列題解之四）：

可以把連接老根和新根的splay看作一個無法彎曲的桿子，其他splay都是連接在桿子上的塊。旋轉操作雖然會改變桿子上每一點的深度，但是卻不會改變塊和桿子上連接點的相對深度關系。所以不會這樣變換老根和新根不會對樹的結構造成破壞。

代碼

洛谷3690

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #define maxn (int)(3e5+1000) int f[maxn],v[maxn],s[maxn],st[maxn],c[maxn][2]; bool r[maxn]; using namespace std; int n,m; void pushr(int x){swap(c[x][0],c[x][1]);r[x]^=1; } void pushdown(int x){if(!r[x])return;if(c[x][0])pushr(c[x][0]);if(c[x][1])pushr(c[x][1]);r[x]=0; } void pushup(int x){s[x]=s[c[x][0]]^s[c[x][1]]^v[x]; }bool nroot(int x){return c[f[x]][0]==x||c[f[x]][1]==x; } void rotate(int x){int y=f[x],z=f[y],k=(c[y][1]==x),w=c[x][!k];bool flag=nroot(y);c[y][k]=c[x][!k];f[c[x][!k]]=y;c[x][!k]=y;f[y]=x;if(flag)c[z][c[z][1]==y]=x;f[x]=z;pushup(y);pushup(x); } void splay(int x){int y=x,z=0;st[++z]=y;while(nroot(y))st[++z]=y=f[y];while(z)pushdown(st[z--]);for(;nroot(x);rotate(x)){y=f[x];if(!nroot(f[x]))continue;rotate((c[f[x]][0]==x)==(c[f[y]][0]==y)?y:x);}// pushup(x); } void access(int x){for(int y=0;x;y=x,x=f[x]){splay(x);c[x][1]=y;pushup(x);} } int findroot(int x){access(x);splay(x);while(c[x][0]){pushdown(x);x=c[x][0];}splay(x);return x; } void makeroot(int x){access(x);splay(x);pushr(x); } void split(int x,int y){makeroot(x);access(y);splay(y); } void link(int x,int y){if(findroot(x)!=findroot(y)){makeroot(x);f[x]=y;} } void cut(int x,int y){makeroot(x);if(findroot(y)==x&&f[y]==x&&!c[y][0]){f[y]=c[x][1]=0;pushup(x);} } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&v[i]);for(int i=1;i<=m;i++){int ty,x,y;scanf("%d%d%d",&ty,&x,&y);if(ty==0){split(x,y);printf("%d\n",s[y]);}else if(ty==1){link(x,y);}else if(ty==2){cut(x,y);}else if(ty==3){splay(x);v[x]=y;//pushup(x);}} }

轉載于:https://www.cnblogs.com/GavinZheng/p/11149166.html

總結

以上是生活随笔為你收集整理的[算法模版]Link-Cut-Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。