免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開APP
userphoto
未登錄

開通VIP,暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP
【洛谷日?qǐng)?bào)#129】淺談Link-Cut Tree

對(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))

LCT

那么現(xiàn)在每個(gè)結(jié)點(diǎn)都是一顆 Splay。

就像這樣:

LCT

如果我們將1,2連接起來(lái)的話。

那么1,2就是同一個(gè) Splay 中的節(jié)點(diǎn)了。

那么現(xiàn)在的情況就是這樣:

LCT

相信你一定對(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 一些操作

Link-Cut Tree 支持以下幾種基本操作:

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所在原樹拆開(切斷)

  • Access(x):

    這是最基礎(chǔ)的操作,意思是將點(diǎn)x到原樹中根結(jié)點(diǎn)root之間的鏈丟到一個(gè)輔助樹splay里面

    比方說(shuō),現(xiàn)在森林的狀態(tài)是這樣的:

LCT

我們的 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的爸爸,所以xSplay中是f[x]的右兒子。

所以就變成了這樣:

LCT

我們將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ò)程:

LCT

虛邊:兒子認(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);//兒子有變化,更新
    }
}

  • findroot(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)兒子

Q:為什么是 makeroot(x) 而不是 access(x) 然后 splay(x) 呢?

A:見下圖:


  • cut(x,y):

    首先我們先把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;
}

  • 0X03 Splay的改動(dòng):

  • 旋轉(zhuǎn)的改動(dòng):

    這里需要注意一下,如果x的父親節(jié)點(diǎn)的父親節(jié)點(diǎn)y已經(jīng)不在當(dāng)前的這棵輔助樹上,只需要連單向邊(也就是虛邊,認(rèn)父不認(rèn)子),否則正常連就行,這里要和普通的rotate區(qū)分開來(lái)。

做個(gè)對(duì)比:

現(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的改動(dòng)

    同樣要注意一下只能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
}


  • 0X04 一些題目代碼:

  • ## P3690 【模板】Link Cut Tree(動(dòng)態(tài)樹)(模板題)

就是上文講的。

Code:

#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)那么難。

Code:

#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)


如果還有不明白的地方,請(qǐng)私信 Qiuly。


洛谷日?qǐng)?bào)接受投稿,采用后有薄禮奉送,請(qǐng)戳 https://www.luogu.org/discuss/show/47327 .




本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊舉報(bào)。
打開APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
動(dòng)態(tài)樹Link-Cut-Tree
Trie樹
數(shù)據(jù)結(jié)構(gòu)之伸展樹 | 董的博客
C語(yǔ)言難點(diǎn)分析整理
LuoguP6218 [USACO06NOV] Round Numbers S
IvanHome--編譯原理之詞法分析器-----pass!
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長(zhǎng)圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服