“會(huì)動(dòng)的動(dòng)態(tài)樹”這種說(shuō)法最早出現(xiàn)在 nehzilrz神犇的blog里。linkcuttree 是解決動(dòng)態(tài)樹問(wèn)題的有力武器之一。 他的特點(diǎn)是非常好寫， 一般來(lái)說(shuō)

100行左右就可以實(shí)現(xiàn)很多功能。但是，如果只是解決一些 “不動(dòng)樹”上的統(tǒng)計(jì)問(wèn)題，動(dòng)態(tài)樹就有點(diǎn)大材小用了。會(huì)動(dòng)的動(dòng)態(tài)樹并不常見，原因是這東西沒(méi)有被普及。但是在各種比賽中，由于功能強(qiáng)大，它被廣泛地應(yīng)用在騙分程序中。(下文中的Access操作等價(jià)于某些論文中的Expose操作)說(shuō)幾道裸題SDOI2008cave這題要求支持linkcutfindroot三個(gè)操由于linkcut的存在各種離線算法分塊算法都很難解決本題的標(biāo)準(zhǔn)做法就是動(dòng)態(tài)樹(當(dāng)然那些暴力和并查集。。。我就不說(shuō)啥了。。。)首先考慮findroot這個(gè)是非常簡(jiǎn)單的access一個(gè)點(diǎn)然后在他當(dāng)前所屬的splay中不停往左走這個(gè)非常顯然cut操作也是很簡(jiǎn)簡(jiǎn)單的主要是要把x(兒子),y(父親)放到同一顆splay中的相鄰位置那么我們先access(x)然后splay(y)這時(shí)候x在y的右邊(而且y的右子樹只有這一個(gè)點(diǎn))此時(shí)斷開x和y的連接即可link就有些麻煩了，原因是x點(diǎn)有可能已經(jīng)有一個(gè)父親了，由于樹中父親的唯一性，你不可能給他安上第二個(gè)父親這時(shí)候就需要一點(diǎn)措施來(lái)保證x沒(méi)有父親做法是access(x)splay(x)在x上打一個(gè)翻轉(zhuǎn)標(biāo)記注意到打翻轉(zhuǎn)標(biāo)記之后當(dāng)前鏈上的父子關(guān)系全部倒置導(dǎo)致x成為了這段鏈上深度最小的這時(shí)候給他按父親就很容易了會(huì)動(dòng)的動(dòng)態(tài)樹還有一題就是COCI的OTOCI(當(dāng)然這題的標(biāo)準(zhǔn)做法是離線，這里不談)我一直覺得會(huì)動(dòng)的動(dòng)態(tài)樹只需要會(huì)上面的即可但是這幾天注意到了一個(gè)非常嚴(yán)重的問(wèn)題先說(shuō)說(shuō)WC2012mst一題的30分也就是只能-1邊權(quán)的由于我比較二考場(chǎng)上YY了一個(gè)非常二逼的做法排序所有邊將權(quán)值相同的一起處理foreachedge如果當(dāng)前邊連接了兩個(gè)不連通的點(diǎn)用一條未染色邊link兩點(diǎn)否則ans+=當(dāng)前這兩點(diǎn)間路徑上未染色的邊數(shù)同時(shí)將路徑上所有邊置為已染色權(quán)值相同的邊處理完畢后將所有邊置為已染色邊權(quán)問(wèn)題可以通過(guò)在兒子上記錄變成點(diǎn)權(quán)染色的問(wèn)題可以用標(biāo)記解決link操作用動(dòng)態(tài)樹解決看起來(lái)是非常好搞的但是我考場(chǎng)上寫了4個(gè)小時(shí)多發(fā)現(xiàn)這里面有非常嚴(yán)重的問(wèn)題在翻轉(zhuǎn)一段路徑之后以前記錄在兒子上的點(diǎn)權(quán)現(xiàn)在要記錄在父親上(也就是說(shuō)新的兒子)考場(chǎng)上我并沒(méi)有想出這個(gè)問(wèn)題應(yīng)該怎么實(shí)現(xiàn)后來(lái)咨詢了神牛得出了兩種方法1、將以前的邊變成點(diǎn)(共2*n-1點(diǎn))(frommike_nzk)2、實(shí)時(shí)記錄當(dāng)前到路徑上兒子的邊權(quán)這里主要說(shuō)第二個(gè)做法路徑的改變僅會(huì)發(fā)生在 access的時(shí)候 也就說(shuō)我們?cè)?access的時(shí)候維護(hù)一下這個(gè)值就好了在access

的時(shí)候 怎么維護(hù)呢？這個(gè)問(wèn)題我并沒(méi)有太好的解決方案

目前想到的做法是

在access的時(shí)候

找到新接上上的子樹中深度最小的這樣做的復(fù)雜度也許是 log^2N同時(shí)在處理 reverse標(biāo)記的時(shí)候

也有可能在某種均攤分析之后變?yōu)?logN也應(yīng)該做些許修改 在交換兩個(gè)兒子的同時(shí)

交換向上

(到父親的邊權(quán)

)和向下(到兒子上的邊權(quán))的值附：邊權(quán)會(huì)動(dòng)樹部分代碼voidrev(){if(this==a)return;_rev^=1;swap(val[0],val[1]);swap(maxv[0],maxv[1]);swap(c[0],c[1]);}Tedgeintreego(){push();if(c[0])returna[c[0]].go();elsereturnval[0];}intaccess(intx){intp=0,q=x;Tedgeintreeret;while(q){splay(q);if(A[q].f==0)ret=max(A[p].maxv[0],A[A[q].c[1]].maxv[0]);A[A[q].c[1]].isroot=true;A[p].isroot=false;A[q].c[1]=p;A[q].val[1]=A[p].go();A[q].update();p=q;q=A[q].f;}returnret.who;}voidevert(intx){access(x);splay(x);A[x].rev();}voidlink(intx,inty,intw){evert(x);A[x].val[0].who=w;A[x].f=y;}voidcut(intx,inty,intw){splay(x);if(!(A[x].val[0]==w))swap(x,y);access(x);splay(y);A[y].c[1]=0;A[y].val[1].who=0;A[y].update();A[x].val[0].who=0;A[x].f=0; A[x].isroot=true;A[x].update();}BZOJ上的2594是為了測(cè)試這種動(dòng)態(tài)樹的一道不錯(cuò)的題目。我終于會(huì)寫會(huì)動(dòng)的動(dòng)態(tài)樹了！以前寫的Link-CutTree 都是處理形態(tài)不變的樹 ..那種情形其實(shí)樹鏈剖分更合適的。關(guān)于會(huì)動(dòng)的動(dòng)態(tài)樹 推薦kAc牛寫的詳解 傳送門戳這里我這里用個(gè)例子配個(gè)圖解釋一下 Link操作。*先來(lái)一些注釋..關(guān)于圖中邊的表示實(shí)線為重邊虛線為輕邊(2)本文的Access操作等價(jià)于某些論文里的 Expose操作(3)Splay(x)指把x節(jié)點(diǎn)提到所在 splay樹的根形態(tài)示意圖上當(dāng)然不可能體現(xiàn)出還沒(méi)有執(zhí)行的反轉(zhuǎn)懶標(biāo)記，因此只畫出我們所期望的、反轉(zhuǎn)全部執(zhí)行完畢的樣子假設(shè)有一棵樹如圖(1)，現(xiàn)在要新增一條邊<2,5>。第一步，

Access(2)

樹變?yōu)閳D

(2)的樣子。第二步，

Reverse(2)

在2號(hào)點(diǎn)上打一個(gè)反轉(zhuǎn)標(biāo)記并立即執(zhí)行

(所謂執(zhí)行，就是交換左右節(jié)點(diǎn)并下傳反轉(zhuǎn)標(biāo)記)

如圖(3)注意Splay上反轉(zhuǎn)意味著什么 ——Splay的先序遍歷同時(shí)也是一條重路徑上節(jié)點(diǎn)按遠(yuǎn)離根節(jié)點(diǎn)方向排列的序列，因此，這個(gè)反轉(zhuǎn)操作實(shí)際上倒轉(zhuǎn)了這條鏈上的父子關(guān)系，讓

2號(hào)點(diǎn)成為所在樹的根節(jié)點(diǎn)。第三步，把

2的父親置為

5(

我習(xí)慣上弄成輕邊

)

完成了

Link

操作 如圖(4)這就是Link操作的實(shí)現(xiàn)。其余的Cut和findroot 比較好理解就不廢話了。SDOI2008Cave 洞穴勘測(cè) (BZOJ2049)是不錯(cuò)的模板題。我的代碼偏慢 ...靠著

inline

勉強(qiáng)進(jìn)了

4s..================================================================================================={$inlineon}programbzoj_2049;{[Sdoi2008]cave}constfin=0;maxn=12000;varn,m:longint;typept=^node;node=recordc:array[0..1]ofpt;f:pt;d:byte;r:boolean;end;varTnull:node;null:pt;proceduresc(x,t:pt;d:byte);inline;beginx^.c[d]:=t;ift=nullthenexit;t^.f:=x;t^.d:=d;end;vara:array[1..maxn]ofnode;procedurepus(x:pt);inline; //執(zhí)行并下傳標(biāo)記vart:pt;beginifx=nullthenexit;ifnotx^.rthenexit;t:=x^.c[0];x^.c[0]:=x^.c[1];x^.c[1]:=t;ifx^.c[0]<>nullthenbeginx^.c[0]^.d:=0;x^.c[0]^.r:=x^.c[0]^.rxortrue;end;ifx^.c[1]<>nullthenbeginx^.c[1]^.d:=1;x^.c[1]^.r:=x^.c[1]^.rxortrue;end;x^.r:=false;end;procedureupd(x:pt);inline; //更新節(jié)點(diǎn)信息(雖然這道題沒(méi)什么要維護(hù)的信息，但直覺上這幾個(gè)作還是需要的)

pus操beginifx=nullthenexit;pus(x);pus(x^.c[0]);pus(x^.c[1]);end;procedurerot(x:pt);inline; //將x旋轉(zhuǎn)到其父親的位置vary:pt;d:byte;beginy:=x^.f;pus(y);pus(x);d:=x^.d;sc(y,x^.c[dxor1],d);ify^.d=2thenbeginx^.f:=y^.f;x^.d:=2;endelsesc(y^.f,x,y^.d);sc(x,y,dxor1);upd(y);upd(x);end;procedurespl(x:pt); //把x提到根beginpus(x);whilex^.d<>2dobeginifx^.f^.d=2thenrot(x)elsebeginif(x^.dxorx^.f^.d=1)xorx^.f^.rthenbeginrot(x);rot(x);endelsebeginrot(x^.f);rot(x);end;end;end;upd(x);end;procedureacc(v:pt); //Access操作varu:pt;beginu:=v;v:=null;whileu<>nulldobeginspl(u);upd(u);ifu^.c[1]<>nullthenu^.c[1]^.d:=2;sc(u,v,1);upd(u);v:=u;u:=u^.f;end;end;procedurelnk(x,y:pt);

//Link

操作varu:pt;beginacc(x);spl(x);x^.r:=x^.rxortrue;pus(x);x^.f:=y;end;procedurecut(x,y:pt);

//Cut

操作varu:pt;beginacc(x);spl(x);u:=y;whileu^.d<>2dou:=u^.f;ifx<>uthenbeginu^.f:=null;exit;end;u:=x;x:=y;y:=u;acc(x);spl(x);u:=y;whileu^.d<>2dou:=u^.f;ifx<>uthenbeginu^.f:=null;exit;end;end;functionqry(x,y:pt):boolean; //本題的Query(x,y)判斷Findroot(x)==Findroot(y)varu,v:pt;beginacc(x);u:=x;whileu^.d<>2dou:=u^.f;whiletruedobeginpus(u); //注意，反轉(zhuǎn)標(biāo)記會(huì)改變 splay中的左右子節(jié)點(diǎn)，因而 findroot 要小心一些ifu^.c[0]<>nullthenu:=u^.c[0]elsebreak;end;acc(y);v:=y;whilev^.d<>2dov:=v^.f;whiletruedobeginpus(v);ifv^.c[0]<>nullthenv:=v^.c[0]elsebreak;end;qry:=(u=v);end;procedureinit;vari:longint;beginnull:=@Tnull;Tnull.c[0]:=null;Tnull.c[1]:=null;Tnull.f:=null;Tnull.r:=false;readln(n,m);fori:=1tondobegina[i]:=Tnull;a[i].d:=2;end;end;proceduresolve;varch,tch:char;x,y:longint;u,v:pt;beginwhilem>0dobegindec(m);read(ch);whilepos(ch,'QCD')=0doread(ch);read(tch);whiletch<>''doread(tch);readln(x,y);u:=@a[x];v:=@a[