對(duì)于findroot最后要Splay的問(wèn)題，最后還是將找到的根節(jié)點(diǎn)Splay一下到Splay樹的根節(jié)點(diǎn)，不然可能會(huì)被一些毒瘤卡。(雖然我做了幾題，最后沒(méi)Splay的代碼也A了)感謝管理員ComeIntoPower大大提出的兩個(gè)紕漏!在此致謝!)(還有一個(gè)已在正文修改))
Code:
inline int findroot(int x){
Access(x);//Access將x和根結(jié)點(diǎn)搞到同一個(gè)Splay中
Splay(x);//轉(zhuǎn)到Splay的根結(jié)點(diǎn)
while(ch[x][0])pushdown(x),x=ch[x][0];//不斷的找左兒子&更新節(jié)點(diǎn)信息
Splay(x);//Splay到Splay樹根節(jié)點(diǎn)。
return x;//最左邊的就是根結(jié)點(diǎn)了。
}
那么我們開始正文。
0XFF 前言&概念
Link-Cut Tree 是一種用來(lái)維護(hù)動(dòng)態(tài)森林連通性的數(shù)據(jù)結(jié)構(gòu)，適用于動(dòng)態(tài)樹問(wèn)題。它采用類似樹鏈剖分的輕重邊路徑剖分，把樹邊分為實(shí)邊和虛邊，并用 Splay 來(lái)維護(hù)每一條實(shí)路徑。Link-Cut Tree 的基本操作復(fù)雜度為均攤O(logn)，但常數(shù)因子較大，一般效率會(huì)低于樹鏈剖分。但是卻可以解決樹鏈剖分解決不了的問(wèn)題(或者優(yōu)化碼量) -----Menci dalao
動(dòng)態(tài)樹LCT(link cut tree)是一個(gè)可以動(dòng)態(tài)維護(hù)森林上各種信息的東西(刪除查找合并啥的都有吧)，原來(lái)的森林我們稱為原森林，里面有實(shí)邊和虛邊，為啥有這兩種邊呢，首先LCT是用很多個(gè)splay維護(hù)這個(gè)森林的信息，那么因?yàn)閟play本來(lái)就是個(gè)二叉樹，所以我們要將原森林”剖分”成很多個(gè)二叉樹并且用splay來(lái)維護(hù)它，用實(shí)邊連接起來(lái)的一棵樹就是原森林中的一棵樹，我們稱它為原樹。
這個(gè)Splay會(huì)有些特殊，它的關(guān)鍵字是節(jié)點(diǎn)在樹里面的深度。
這棵原樹我們也不是直接用splay維護(hù)，而是按每個(gè)點(diǎn)在原樹中的深度為優(yōu)先級(jí)，將每個(gè)點(diǎn)以優(yōu)先級(jí)的中序遍歷丟到splay上。我們一般將原樹所對(duì)應(yīng)的splay稱為輔助樹，原森林就對(duì)應(yīng)一個(gè)輔助樹森林。
-----quhengyi11 dalao
請(qǐng)務(wù)必先將上文讀清楚，再繼續(xù)下面的閱讀。
Splay是輔助樹，閱讀時(shí)不要將主的和輔的搞混了。
顯然原樹中同一個(gè)深度的點(diǎn)是不可能在一個(gè)splay里的，因此每個(gè)splay里面就是維護(hù)了原樹中的一條鏈
Link-Cut Tree 準(zhǔn)確的說(shuō)是一個(gè) Splay 森林。每棵 Splay 都用'虛邊'鏈接(下圖灰邊表示虛邊)，每棵 Splay 中的結(jié)點(diǎn)都用'實(shí)邊'鏈接起來(lái)(下圖用黑色表示實(shí)邊)。假如我們現(xiàn)在有一個(gè)栗子：(用紅色圈圈圈在一起的結(jié)點(diǎn)是一個(gè) Splay 中的結(jié)點(diǎn))
那么現(xiàn)在每個(gè)結(jié)點(diǎn)都是一顆 Splay。
就像這樣：
如果我們將1,2連接起來(lái)的話。
那么1,2就是同一個(gè) Splay 中的節(jié)點(diǎn)了。
那么現(xiàn)在的情況就是這樣：
相信你一定對(duì)此有些了解了吧。
0X01 一些基本的定義
f[x]:結(jié)點(diǎn)x的爸爸(father)
v[x]:結(jié)點(diǎn)x的權(quán)值(value)
s[x]:結(jié)點(diǎn)x及它的子樹的權(quán)值和(sum)
r[x]:結(jié)點(diǎn)x的翻轉(zhuǎn)情況(rev)
ch[x][0/1]:結(jié)點(diǎn)x的左/右兒子
# 0X02 一些操作
Access(x)：將x到根節(jié)點(diǎn)的路徑上全部變成實(shí)邊，并棄掉自己所有的兒子(變成虛邊：認(rèn)父不認(rèn)子)(每一個(gè)父結(jié)點(diǎn)對(duì)于自己的每個(gè)子結(jié)點(diǎn)只有一條實(shí)邊)
findroot(x):找出x所在的原樹的根結(jié)點(diǎn)(實(shí)際上就是上圖的一號(hào)點(diǎn))
makeroot(x):這個(gè)操作的意思是將x點(diǎn)變?yōu)樵瓨涞母?jié)點(diǎn)
split(x,y):將x,y搞在一個(gè) Splay 中，以方便操作。
link(x,y):將x和y所在原樹合并起來(lái)(鏈接)
cut(x,y):將x和y所在原樹拆開(切斷)
這是最基礎(chǔ)的操作，意思是將點(diǎn)x到原樹中根結(jié)點(diǎn)root之間的鏈丟到一個(gè)輔助樹splay里面
比方說(shuō)，現(xiàn)在森林的狀態(tài)是這樣的：
我們的 x 現(xiàn)在等于6。執(zhí)行 Access(6) 。
那么就會(huì)將{1-3，3-6}變成實(shí)邊，1-2變成虛邊，假設(shè)6有一兒子n，之間用實(shí)邊連著，那么這條邊也將變成虛邊。
每次將x點(diǎn) splay 到當(dāng)前所在輔助樹的根節(jié)點(diǎn)，將它的右兒子更新為上一個(gè)x，然后令x跳到它的父節(jié)點(diǎn)，特別的，第一個(gè)x的右兒子設(shè)為0(NULL)。
Q：為什么是右兒子而不是左兒子呢？
A：因?yàn)?span>f[x]的深度小于x，而在Splay里面f[x]是x的爸爸，所以x在Splay中是f[x]的右兒子。
所以就變成了這樣：
我們將x旋轉(zhuǎn)到輔助樹的根節(jié)點(diǎn)，也就是將當(dāng)前原樹這條鏈上深度小于x(在x上面的點(diǎn))丟到了x的左子樹上，將x的右子樹設(shè)為上一個(gè)x點(diǎn)相當(dāng)于將x原來(lái)的右子樹丟到了新的 splay 里面(而它們之間用虛邊相連)，并且將上一段鏈連接起來(lái)。
現(xiàn)在就可以了。這棵新 Splay 中只有這條鏈上的結(jié)點(diǎn)，沒(méi)有其他任何的結(jié)點(diǎn)。如果我們指定要這三個(gè)結(jié)點(diǎn)同時(shí)進(jìn)行操作，可以直接下傳懶標(biāo)記到這三個(gè)結(jié)點(diǎn)組成的 Splay 的根結(jié)點(diǎn)哦!到后面Splay的時(shí)候就可以直接下傳跟新結(jié)點(diǎn)信息了。
總體過(guò)程：
虛邊：兒子認(rèn)父，父不認(rèn)子
實(shí)邊：兒子認(rèn)父，父也認(rèn)子
用FlashHu大佬的話來(lái)說(shuō)，就是四步：
1.轉(zhuǎn)到根。
2.換兒子。
3.更新信息。
4.當(dāng)前操作點(diǎn)切換為輕邊所指的父親，轉(zhuǎn)1。
代碼實(shí)現(xiàn)：
inline void Access(int x){
for(register int y=0;x;y=x,x=f[x]){
Splay(x);//轉(zhuǎn)到所在Splay的根節(jié)點(diǎn)
ch[x][1]=y;//認(rèn)兒子了
pushup(x);//兒子有變化，更新
}
}
首先要明白：
根節(jié)點(diǎn)是的深度最小的
我們可以通過(guò)x向上找，用 Access 操作可以將x和x的根結(jié)點(diǎn)搞到一個(gè) Splay 里。
又因?yàn)橛蠦ST的性質(zhì)：x的左子樹所有結(jié)點(diǎn)的權(quán)值 < x < x右子樹所有結(jié)點(diǎn)的權(quán)值。
而我們又知道，在執(zhí)行完 Access 操作后，這課 Splay 里面的結(jié)點(diǎn)權(quán)值最大的(深度最大的)就是x。
于是我們可以將x Splay 到這棵 Splay 的根結(jié)點(diǎn)，那么現(xiàn)在最左邊的節(jié)點(diǎn)便是這課樹的根結(jié)點(diǎn)了。
代碼實(shí)現(xiàn)：
inline int findroot(int x){
Access(x);//Access將x和根結(jié)點(diǎn)搞到同一個(gè)Splay中
Splay(x);//轉(zhuǎn)到Splay的根結(jié)點(diǎn)
while(ch[x][0])pushdown(x),x=ch[x][0];//不斷的找左兒子&更新節(jié)點(diǎn)信息
return x;//最左邊的就是根結(jié)點(diǎn)了。
}
makeroot(x):
將x到根結(jié)點(diǎn)的路徑上的點(diǎn)全部翻轉(zhuǎn)(即x變成了根節(jié)點(diǎn))
具體操作是我們先將x點(diǎn)與原樹中的根打通一條鏈，那么現(xiàn)在它們就在同一棵輔助樹里面了，我們發(fā)現(xiàn)x一定是在它所在的輔助樹的中序遍歷的最后一個(gè)的(因?yàn)樗沁@條鏈上最深的點(diǎn))，我們把x點(diǎn) splay 到輔助樹的根上，那么x顯然是沒(méi)有右子樹的，我們要實(shí)現(xiàn)將x移到原樹的根上，也就是將x到根的這條鏈的深度全部翻轉(zhuǎn)一遍，在輔助樹上的體現(xiàn)就是將整棵樹翻轉(zhuǎn)一遍，我們可以寫個(gè)翻轉(zhuǎn)標(biāo)記來(lái)減少?gòu)?fù)雜度。
代碼實(shí)現(xiàn)：
inline void filp(int x){//Splay普通區(qū)間翻轉(zhuǎn)
swap(ch[x][0],ch[x][1]);r[x]^=1;
}
inline void makeroot(int x){
Access(x);
Splay(x);
filp(x);//懶標(biāo)記&翻轉(zhuǎn)區(qū)間
}
split(x,y)
這個(gè)操作是將x到y(tǒng)之間的那條路徑丟到一棵輔助樹里，并且這棵輔助樹以y節(jié)點(diǎn)為根(方便處理信息)。
Splay 維護(hù)的是原樹中的一條鏈，我們不能保證x,y會(huì)在同一條鏈里。
所以我們可以先把x變成原樹的根節(jié)點(diǎn)(這下子Access(y)就會(huì)將x到y(tǒng)之間的所有節(jié)點(diǎn)丟到一個(gè) Splay 中了)。
最后如上面所講的，最后來(lái)一個(gè) Splay(y) 就大功告成了。
代碼實(shí)現(xiàn)：
inline void split(int x,int y){
makeroot(x);Access(y);Splay(y);
}
link(x,y):
將x和y所在原樹合并起來(lái)(鏈接)
首先將x點(diǎn)丟到原樹的根，然后去找找y的根是不是x，如果不是說(shuō)明x,y不在一個(gè)原樹內(nèi)，我們將x的父節(jié)點(diǎn)設(shè)為y，也就相當(dāng)于從y到x連了一條虛邊。
代碼實(shí)現(xiàn)：
inline void link(int x,int y){
makeroot(x);//丟到根
if(findroot(y)!=x)f[x]=y;//鏈接一條虛邊
//注意因?yàn)槭翘撨?，所以不能認(rèn)兒子
首先我們先把x,y之間的那條邊用split(x,y)拎出來(lái)，因?yàn)閤,y是相鄰的，所以y的左兒子一定是x，將它們的父子關(guān)系消滅掉即可。
消滅父子關(guān)系時(shí)一定滿足以下條件：
1.x和y在一個(gè)原樹里(不在一個(gè)樹里面往哪兒切啊)
2.split之后x是y的左兒子
3.x的右兒子是空的(保證了中序遍歷中y緊跟在x的后面，即深度相鄰)(x的權(quán)值(深度)只比y小1，而x又正好是直接連著y的，所以我們無(wú)法再找到 >x 而又 <y 的整數(shù)了)
代碼實(shí)現(xiàn)：
inline void cut(int x,int y){
split(x,y);
if(findroot(y)==x&&f[x]==y&&!ch[x][1]){//判斷各種條件
f[x]=ch[y][0]=0;//徹底切斷關(guān)系
pushup(y);//兒子變了，更新
}return;
}
這里需要注意一下，如果x的父親節(jié)點(diǎn)的父親節(jié)點(diǎn)y已經(jīng)不在當(dāng)前的這棵輔助樹上，只需要連單向邊(也就是虛邊，認(rèn)父不認(rèn)子)，否則正常連就行，這里要和普通的rotate區(qū)分開來(lái)。
現(xiàn)在的rotate(x):
這里的x可以不更新，因?yàn)闀?huì)在下一次rotate時(shí)更新。----管理員ComeIntoPower大大
謝謝管理員ComeIntoPower大大!
inline void rotate(int x){
int y=f[x],z=f[y],k=chk(x),v=ch[x][!k];
if(get(y))ch[z][chk(y)]=x;ch[x][!k]=y,ch[y][k]=v;
if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y);
}
普通的rotate(x):
inline void rotate(int x){
int y=f[x],z=f[y],k=chk(x),v=ch[x][!k];
ch[z][chk(y)]=x;ch[x][!k]=y,ch[y][k]=v;
f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);
}
同樣要注意一下只能Splay到輔助樹的根節(jié)點(diǎn)，Splay之前需先下傳一下這一條鏈上需操作的所有的點(diǎn)，用棧來(lái)完成即可，可以手寫棧來(lái)減少常數(shù)。
inline void Splay(int x){
int y=x,top=0;hep[++top]=y;
while(get(y))hep[++top]=y=f[y];
while(top)pushdown(hep[top--]);
while(get(x)){//基本普通的Splay
y=f[x],top=f[y];
if(get(y))
rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
rotate(x);
}pushup(x);return;
}
## P3690 【模板】Link Cut Tree（動(dòng)態(tài)樹）(模板題)
就是上文講的。
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define A printf('A')
#define C printf(' ')
using namespace std;
const int N=3e5+2;
template <typename Tp> inline void IN(Tp &x){
int f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=f;
}int f[N],v[N],s[N],r[N],hep[N],ch[N][2];
inline int get(int x){
return ch[f[x]][0]==x||ch[f[x]][1]==x;
}
inline void pushup(int x){
s[x]=s[ch[x][1]]^s[ch[x][0]]^v[x];
}
inline void filp(int x){
swap(ch[x][0],ch[x][1]);r[x]^=1;
}
inline void pushdown(int x){
if(!r[x])return;r[x]=0;
if(ch[x][0])filp(ch[x][0]);
if(ch[x][1])filp(ch[x][1]);
}
inline void rotate(int x){
int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k];
if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;
if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);
}
inline void Splay(int x){
int y=x,top=0;hep[++top]=y;
while(get(y))hep[++top]=y=f[y];
while(top)pushdown(hep[top--]);
while(get(x)){
y=f[x],top=f[y];
if(get(y))
rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
rotate(x);
}pushup(x);return;
}
inline void Access(int x){
for(register int y=0;x;x=f[y=x])
Splay(x),ch[x][1]=y,pushup(x);
}
inline void makeroot(int x){
Access(x);Splay(x);filp(x);
}
inline int findroot(int x){
Access(x);Splay(x);
while(ch[x][0])pushdown(x),x=ch[x][0];
return x;
}
inline void split(int x,int y){
makeroot(x);Access(y);Splay(y);
}
inline void link(int x,int y){
makeroot(x);if(findroot(y)!=x)f[x]=y;
}
inline void cut(int x,int y){
split(x,y);
if(findroot(y)==x&&f[x]==y&&!ch[x][1]){
f[x]=ch[y][0]=0;pushup(y);
}return;
}int n,m,x,y,op;
int main(){
scanf('%d%d',&n,&m);
for(register int i=1;i<=n;++i)scanf('%d',&v[i]);
for(register int i=1;i<=m;++i){
scanf('%d%d%d',&op,&x,&y);
if(op==0)split(x,y),printf('%d\n',s[y]);
else if(op==1)link(x,y);
else if(op==2)cut(x,y);
else Splay(x),v[x]=y;
}return 0;
}
## P2147 [SDOI2008]洞穴勘測(cè)
分析：題目只要求link(有一條新道路==連接)和cut(道路被摧毀了==cut)以及判斷連通性(直接findroot，一樣的話那么就是聯(lián)通的)
就是LCT的板子，真的沒(méi)那么難。
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define A printf('A')
#define C printf(' ')
using namespace std;
const int N=2e5+2;
template <typename Tp> inline void IN(Tp &x){
int f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=f;
}int n,m,f[N],r[N],hep[N],ch[N][2];
inline int get(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
inline void filp(int x){swap(ch[x][0],ch[x][1]);r[x]^=1;}
inline void pushdown(int x){
if(!r[x])return;r[x]=0;
if(ch[x][0])filp(ch[x][0]);
if(ch[x][1])filp(ch[x][1]);
}
inline void rotate(int x){
int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k];
if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;
if(v)f[v]=y;f[y]=x,f[x]=z;return;
}
inline void Splay(int x){
int y=x,top=0;hep[++top]=y;
while(get(y))hep[++top]=y=f[y];
while(top)pushdown(hep[top--]);
while(get(x)){
y=f[x],top=f[y];
if(get(y))
rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
rotate(x);
}return;
}
inline void Access(int x){
for(register int y=0;x;x=f[y=x])
Splay(x),ch[x][1]=y;
}
inline void makeroot(int x){
Access(x);Splay(x);filp(x);
}
inline int findroot(int x){
Access(x);Splay(x);
while(ch[x][0])pushdown(x),x=ch[x][0];
return x;
}
inline void split(int x,int y){
makeroot(x);Access(y);Splay(y);
}
inline void link(int x,int y){
makeroot(x);if(findroot(y)!=x)f[x]=y;
}
inline void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&f[x]==y&&!ch[x][1]){
f[x]=ch[y][0]=0;
}return;
}char op[16];
int main(){
scanf('%d%d',&n,&m);
for(register int x,y,i=1;i<=m;++i){
scanf('%s%d%d',op,&x,&y);
if(op[0]=='C')link(x,y);
else if(op[0]=='D')cut(x,y);
else if(op[0]=='Q'){
if(findroot(x)==findroot(y))printf('Yes\n');
else printf('No\n');
}
}return 0;
}
再推存一道題目:P1501 [國(guó)家集訓(xùn)隊(duì)]Tree II
這道題目主要就是懶標(biāo)記的運(yùn)用，建議在做這一道題之前先去做一做線段樹的模板2，其實(shí)道理差不多，相通的，并不難。(講乘法標(biāo)記的正確下傳方法弄到Splay的下傳上即可)
當(dāng)然這道題我也附上題解：題解 P1501【[國(guó)家集訓(xùn)隊(duì)]Tree II】(Link-Cut-Tree)
0X05 致謝：
### 感謝FlashHu大佬的文章:LCT總結(jié)——概念篇+洛谷P3690[模板]Link Cut Tree(動(dòng)態(tài)樹)（LCT，Splay），這篇文章教會(huì)了我LCT，所以碼風(fēng)可能會(huì)比較像。
### 最后推薦一個(gè)網(wǎng)址，這里面有一些基本的LCT例題以及作者的解析：傳送門
聯(lián)系客服
