文章目錄

• 前言
• 解析
• • 原理
  • rotate(x)
  • splay(x)
  • access(x)
  • findroot(x)
  • makeroot(x)
  • split(x,y)
  • link(x,y)
  • cut(x,y)
  • pushdown(x)
• 完整代碼

所謂Link Cut Tree，就是林可卡特發明的tree

（逃）

前言

終于走到了這一天…
其實感覺沒有預想的那么難（單純就學習算法和理解模板而言）
至少感覺比學平衡樹輕松

LCT是一種很強大的樹形數據結構
最重要的功能優勢就是支持單log的復雜度完成加邊、刪邊、換根的操作
在路徑問題上十分強大

解析

原理

LCT的核心原理是實鏈剖分
和重鏈剖分類似的，將一棵樹中的邊分為實邊和虛邊
每個結點的最多有一條連向兒子的實邊（與樹鏈剖分不同的，也可以沒有）

把實邊連成的鏈成為實鏈
把在同一條實鏈上的結點放到同一個splay中
這個splay的中序遍歷就是這條鏈從上到下的順序
這樣就間接的表示了所有實邊的信息

那么如何表示虛邊？
假設原樹上有一條 $fa$ 指向$son$的虛邊
就把son所在的splay的根節點指向fa，從而表示出虛邊
根節點也有父親了，如何判斷根節點呢？
只有該結點的父親的左右兒子都不是自己，那么這個結點就是根節點

inline bool isroot(int x) {return tr[f[x]][0]!=x&&tr[f[x]][1]!=x; }

下面我們來講講具體的操作函數

rotate(x)

和普通的splay大同小異，唯一需要注意的是有一句

if(gfa) tr[gfa][which(fa)]=x;

變成了：

if(!isroot(fa)) tr[gfa][which(fa)]=x;

較好理解，因為判定根的條件變了

splay(x)

將x轉到所在splay的根節點，由于只需要轉到根一個功能，穿一個參即可
注意：不同于正常的splay，需要先把鏈上的標記下放
實現有兩種方法
第一種是遞歸：

void pushall(int x){//printf("%d\n",x);if(!isroot(x)) pushall(f[x]);pushdown(x); }

第二種是手寫棧：

int y=x,top=0;zhan[++top]=y;while(!isroot(y)) zhan[++top]=y=f[y];

建議使用第二種，因為第一種不小心容易寫完函數后忘記調用（別問我為什么知道）
然后和rotate類似的，對根的判斷略有區別
不過都是一個道理

inline void splay(int x) {int y=x,top=0;zhan[++top]=y;while(!isroot(y)) zhan[++top]=y=f[y];while(top) pushdown(zhan[top--]);for(int fa; fa=f[x],!isroot(x); rotate(x)) {if(!isroot(fa)) which(fa)==which(x)?rotate(fa):rotate(x);}return; }

access(x)

重中之重，LCT的靈魂

功能：提取出 x 到根節點的一條實鏈

先把x的尾巴去掉，具體來說就是轉到根，然后砍掉右子樹
然后一路往上直至 fa 指針為空，過程中需要改變實虛邊的狀態

inline void access(int x) {for(int y(0); x; y=x,x=f[x]) {splay(x);tr[x][1]=y;pushup(x);if(y) f[y]=x;}return; }

findroot(x)

功能：找到x所在的樹的根節點（注意是真實的樹而不是splay的根）

先access(x)，然后把x轉到根，不斷往左走即可

inline int findroot(int x) {access(x);splay(x);while(pushdown(x),tr[x][0]) x=tr[x][0];splay(x);return x; }

makeroot(x)

功能：把x作為其所在樹的根（換根）
前面說過，父子關系在splay中的體現是中序遍歷
所以換根（即顛倒x-rt路徑上所有的父子關系），其實就是區間翻轉
先access(x)，然后轉到根，然后用類似文藝平衡樹的方式在x上打一個翻轉標記即可

inline void makeroot(int x) {access(x);splay(x);tag(x);return; }

（最愉快的代碼）

split(x,y)

功能：提取出以x、y為兩端點的實鏈（前提是二者聯通）

makeroot(x)之后access(y)即可
為了后面方便，常常再加一步splay(y)（不然連根是誰都不知道提取個寂寞）

inline void split(int x,int y){//y is fathermakeroot(x);access(y);splay(y);return; }

link(x,y)

功能：加一條邊$(x,y)$（在有出現環的時候忽略操作）

出現環（即xy原來就聯通）可以用findroot判掉
否則，先makeroot(x)，然后把f(x)指向y即可
記得按需要更新y的信息！

inline void link(int x,int y) {makeroot(x);if(findroot(y)==x) return;f[x]=y;pushup(y);//printf("link: %d -> %d\n",x,y); }

cut(x,y)

功能：切斷邊$(x,y)$（在沒有這條邊時忽略操作）

先makeroot(x)，然后access(y)，splay(y)到根
此時如果存在這條邊，必然x和y是在同一個splay中
判斷的充要條件：x是y的左兒子且x沒有右兒子，比較顯然
如果存在的話，把這條y的左兒子和x的父親賦值為0即可
不要忘記更新y的信息（又一次）

inline void cut(int x,int y) {makeroot(x);access(y);splay(y);if(tr[y][0]!=x||tr[x][1]) return;tr[y][0]=f[x]=0;pushup(y);return; }

pushdown(x)

大部分時候只需要翻轉
一個看到的地方都說比較“穩妥”的寫法
（誰不喜歡穩妥呢）

inline void tag(int x) {if(x) {rev[x]^=1;swap(tr[x][0],tr[x][1]);} } inline void pushdown(int x) {if(rev[x]){rev[x]=0;tag(tr[x][0]);tag(tr[x][1]);}return; }

完整代碼

經驗傳送門

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e5+100; const int mod=1e9+7; const double eps=1e-9; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m;#define ls(o) tr[o][0] #define rs(o) tr[o][1] int tr[N][2],f[N],rev[N],val[N],mx[N]; inline bool isroot(int x) {return tr[f[x]][0]!=x&&tr[f[x]][1]!=x; } inline bool which(int x) {return tr[f[x]][1]==x; } inline void pushup(int x) {if(x){mx[x]=x;if(ls(x)&&val[mx[ls(x)]]>val[mx[x]]) mx[x]=mx[ls(x)];if(rs(x)&&val[mx[rs(x)]]>val[mx[x]]) mx[x]=mx[rs(x)];}return; } inline void tag(int x) {if(x) {rev[x]^=1;swap(tr[x][0],tr[x][1]);} } inline void pushdown(int x) {if(rev[x]){rev[x]=0;tag(tr[x][0]);tag(tr[x][1]);}return; } void debug(int x) {if(!x) return;pushdown(x);debug(tr[x][0]);printf("debug: x=%d ls=%d rs=%d\n",x,tr[x][0],tr[x][1]);debug(tr[x][1]);return; } inline void rotate(int x) {int fa=f[x],gfa=f[fa];int d=which(x),son=tr[x][d^1];f[x]=gfa;if(!isroot(fa)) tr[gfa][which(fa)]=x;f[fa]=x;tr[x][d^1]=fa;if(son){f[son]=fa;}tr[fa][d]=son;pushup(fa);pushup(x);return; } int zhan[N]; inline void splay(int x) {int y=x,top=0;zhan[++top]=y;while(!isroot(y)) zhan[++top]=y=f[y];while(top) pushdown(zhan[top--]);for(int fa; fa=f[x],!isroot(x); rotate(x)) {if(!isroot(fa)) which(fa)==which(x)?rotate(fa):rotate(x);}return; } inline void access(int x) {for(int y(0); x; y=x,x=f[x]) {splay(x);tr[x][1]=y;pushup(x);if(y) f[y]=x;}return; } inline void makeroot(int x) {access(x);splay(x);tag(x);return; } inline int findroot(int x) {access(x);splay(x);while(pushdown(x),tr[x][0]) x=tr[x][0];splay(x);return x; } inline void link(int x,int y) {makeroot(x);if(findroot(y)==x) return;f[x]=y;pushup(y);//printf("link: %d -> %d\n",x,y); } inline void cut(int x,int y) {makeroot(x);access(y);splay(y);if(tr[y][0]!=x||tr[x][1]) return;tr[y][0]=f[x]=0;pushup(y);return; } inline void split(int x,int y){//y is fathermakeroot(x);access(y);splay(y);return; }

總結

以上是生活随笔為你收集整理的模板：Link Cut Tree（LCT）的全部內容，希望文章能夠幫你解決所遇到的問題。

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