集訓隊2006集維護森林連通性

1、維護森林連通性動態(tài)樹華東師大二附中陳首元動態(tài)樹維護一個森林支持邊的插入與刪除支持樹的合并與分離支持尋找路徑上費用最小的邊所有操作的均攤復雜度為O(logN)234567811020-20030-5-5Root(1,2,3,4,5,6,7,8)=1MinCost(6)=10Update(7,10)540Evert(6)新樹根Cut(4)Root(7,8)=4Link(3,4,10)動態(tài)樹的基本操作 Root(v) 返回包含節(jié)點v的樹的根MinCost(v) 返回v到根路徑上費用最小的邊Update(v,x)使v到樹根路徑上的邊的費用+x Link(v,w,x)將以v為根的樹連接到節(jié)點root(w

2、)上，（v,w）的費用為x Cut(v)刪除v與其父節(jié)點連接的邊Evert(v)使v成為新的根，并將v到原樹根上的邊反向操作的實現(xiàn)將樹中的邊分為實邊、虛邊兩種，每個節(jié)點最多向其子節(jié)點連出一條實邊將樹劃分為一些完全由實邊組成的路徑，只對這些路徑進行操作一條路徑頭尾路徑的基本操作Path(v)：返回包含v的路徑 （每個路徑有一個標志）Head(p),Tail(p)：返回首節(jié)點、尾節(jié)點Pmincost(p)：返回p中費用最小的邊Pupdate(p,x:real)：將p中每條邊的費用+xReverse(p)：將p中的每條邊反向Concatenate(p,q,x) ：添加邊(tail(p),head(q

3、)）費用為x，將路徑p,q合并 Split(v)：將v從路徑中刪除并把路徑分為兩部分SpliceSplice(p) ：將路徑p向更靠近根的方向增長實現(xiàn)方法：把虛邊(tail(P),Parent(p) 變?yōu)閷嵾叄瑸榱司S護實邊的性質，將原來從Parent(P)中連出的邊設為虛邊ExposeExpose(v)：將從v到樹根路徑上的所有邊設為實邊 實現(xiàn)方法：不斷調用splice直到根為止有了Expose(v)，就可以實現(xiàn)所有動態(tài)樹操作了Link操作Procedure Link(v,w:vertex;x:real);Begin Concatenate(path(v),expose(w),x);End;C

4、ut操作Function Cut(v:vertex);Var p,q:path; x,y:real;Begin Expose(v); p,q,x,y:=split(v); Dparent(v):=nil; Return y;End;路徑結構用伸展樹保存路徑所有路徑操作都能用Splay實現(xiàn)對于Reverse與PUpdate操作，可以采用先存放修改標志，在訪問時修改的辦法在每次Split和Concatenate操作之后，Splay最左子孫，使它成為根復雜度分析(Expose分析)對于邊v-w（動態(tài)樹中，不是伸展樹中）如果v的子孫w的子孫一半，稱為A類邊，否則成為B類邊。顯然每個點最多連出一條類邊，

5、樹中每條路徑上最多有O(logN)條B類邊。令p為B類邊中的虛邊數。復雜度分析(Expose分析)一次Expose操作，將執(zhí)行數次Splice對于每次Splice：添加一條B類虛邊進入路徑：p+1這種情況最多發(fā)生O(logN)次添加一條A類虛邊進入路徑：p-1可能發(fā)生許多次，但代價是p，p是保持非負的。由上面分析可以看出平均每次expose操作要執(zhí)行O(logN)次路徑操作復雜度分析(Splay分析)勢函數定義r(x)：x在動態(tài)樹中的子節(jié)點數的對數伸展樹的性質：每一次splay操作的均攤復雜度不超過：3(r(t)-r(x)+1 此性質在勢函數定義改變后依然成立復雜度分析Expose的均攤復雜度

6、3(r(root)-r(v)+(v到樹根路徑上的節(jié)點數）由Expose分析得到路徑上的節(jié)點數平均為O(logN)復雜度為O(logN)實現(xiàn)不保存整棵樹，而保存“虛擬樹”。虛擬樹中的頂點與動態(tài)樹中的是一一對應的。虛擬樹中的每個頂點最多連出兩條實邊，其余為虛邊，分別成為左兒子和右兒子，其他頂點稱為中間頂點。完全由實邊組成的子樹稱為實樹。 實現(xiàn)實現(xiàn)expose需要兩種操作：一種是splay，將一棵實樹（也是二叉樹），從某個節(jié)點伸展使這個節(jié)點成為這個實樹的根。第二種是splice，將某個節(jié)點的一個中間節(jié)點變?yōu)樽髢鹤?，左兒子變?yōu)橹虚g節(jié)點。執(zhí)行expose(v)操作需要分為三步。首先沿v往上到虛擬樹的樹根，對沿路的各實樹進行splay，執(zhí)行完這個步后從v到