山東第一試解題報(bào)告

1、解題本題是一個(gè)森林的動(dòng)態(tài)連通性問題，采用并查集或者每次詢問直接遍歷一遍整個(gè)圖的做法之間復(fù)雜度為 O(nm)，實(shí)現(xiàn)得好有可能在本題時(shí)限 4s 內(nèi)通過一半左右的數(shù)據(jù)。一種比較好的解法是采用一種叫作動(dòng)態(tài)樹(Dynamic Tree)的數(shù)據(jù)結(jié)構(gòu)來節(jié)點(diǎn)間的連通情況。整個(gè)森林中各個(gè)動(dòng)態(tài)樹支持以下 5 種操作： Make_Tree()，建立一棵只含有一個(gè)節(jié)點(diǎn)的樹 Evert(v)，使節(jié)點(diǎn) v 成為所在樹的有根樹表示中的樹根Link(u,v)，在節(jié)點(diǎn) u 和節(jié)點(diǎn) v 之間加入一條邊，使這兩個(gè)點(diǎn)所在的樹相互連通。該操兩節(jié)點(diǎn)在操作前不連通。定Cut(u,v)，刪除邊(u,v)。該操定邊(u,v)存在Find_Ro

2、ot(v)，返回節(jié)點(diǎn) v 所在樹的有根樹表示中的樹根動(dòng)態(tài)樹的后四個(gè)操作中都要調(diào)用的一個(gè)操作是 Acs(v)，通過“”節(jié)點(diǎn) v 的方式，將 v 所在的有根樹中從樹根到節(jié)點(diǎn) v 的路徑剖分出來并單獨(dú)。相鄰（也就是在樹中被某條邊連結(jié)）的路徑通過指針 path_parent 連接。由于本問題中初始時(shí)刻沒有任何邊存在，而每次添加、刪除邊操作都必須剖分。相應(yīng)節(jié)點(diǎn)，因而動(dòng)態(tài)樹能保證所有的樹都被一些路徑完全比如某時(shí)刻動(dòng)態(tài)樹所的某棵樹的路徑剖分以及一個(gè)節(jié)點(diǎn)后的路徑剖分如下圖所示（粗線表示剖分的路徑）：圖 1由于每條路徑具有線性次序關(guān)系，又需要頻繁進(jìn)行路徑間的合并、分離、翻轉(zhuǎn)操作，故每條路徑均采用伸展樹(Spla

3、y Tree)實(shí)現(xiàn)，伸展樹點(diǎn)的大小為其在樹中的深度。具體實(shí)現(xiàn)的時(shí)候，不必顯式每個(gè)節(jié)點(diǎn)的深度，只要保證每棵伸展樹的中序遍歷結(jié)果與路徑相同即可。如圖 1 左邊的采用伸展樹路徑后的示意圖如下：圖 2Acs(v)操作要將節(jié)點(diǎn) v 到根節(jié)點(diǎn)的路徑出來，過程分為兩步首先，將 v 在其所在伸展樹中移動(dòng)到根節(jié)點(diǎn)，并將它與其右于節(jié)點(diǎn) v 下方的節(jié)點(diǎn)）分離，并設(shè)置其已經(jīng)被獨(dú)立出來的右點(diǎn) v（也就是在原先的路徑中位的 path_parent 指針指向節(jié)然后，利用 v 所在伸展樹的 path_parent 指針，不斷將 v 所在伸展樹與 path_parent 所指向的伸展樹合并，直到 path_parent 指針懸

4、空為止如此便將從根節(jié)點(diǎn)到節(jié)點(diǎn) v 的路徑剖分出來單獨(dú)了Find_Root(v)操作較為簡(jiǎn)單，節(jié)點(diǎn) v 之后，找到 v 所在的伸展樹中的最小節(jié)點(diǎn)，此即為 v所在有根樹中的深度最小的祖先，也就是樹根Evert(v)操作相當(dāng)于將從樹根到節(jié)點(diǎn) v 的路徑上的所有邊都反向。的伸展樹順序翻轉(zhuǎn)即可。節(jié)點(diǎn) v 之后，將 v 所在Link(u,v)操作需要在兩個(gè)節(jié)點(diǎn)間連接一條邊，由于采用有根樹表示，必須先保證其中一個(gè)是某棵樹的根節(jié)點(diǎn)。此處先將 u 置為所在樹中的根節(jié)點(diǎn)，再將該節(jié)點(diǎn)在其伸展樹中移動(dòng)到根節(jié)點(diǎn)位置。由于 u 已經(jīng)是深度最小的節(jié)點(diǎn)，因而它在伸展樹中的節(jié)點(diǎn)為空。再將節(jié)點(diǎn) v移動(dòng)到伸展樹的根節(jié)點(diǎn)處，然后將

5、v 設(shè)置為 u 的操作。節(jié)點(diǎn)，即完成將 u 設(shè)為 v 的一棵的Cut(u,v)操作時(shí)，首先將 u 置為有根樹的根節(jié)點(diǎn)，從而使 v 一定是 u 的子節(jié)點(diǎn)。節(jié)點(diǎn) v，此時(shí)伸展樹中 v 的樹就是路徑中 v 的祖先部分。將 v 與其樹分離，就實(shí)現(xiàn)了有根樹中刪除邊(u,v)，將一棵樹變?yōu)閮煽脴涞牟僮鳌Ｒ陨纤胁僮骶谏煺箻涞幕静僮?，比如合并、分離、移動(dòng)某個(gè)節(jié)點(diǎn)到樹根位置，這些操作都是均攤時(shí)間復(fù)雜度 O(logn)的。可以證明 Ac s(v)操作對(duì)路徑的改動(dòng)是每次操作均攤 O(1)次，而其他各操作只需要調(diào)用常數(shù)次的 Ac s()以及常數(shù)次的伸展樹基本操作，因此以上每個(gè)操作的均攤時(shí)間復(fù)雜度為 O(logn)有了動(dòng)態(tài)樹數(shù)據(jù)結(jié)構(gòu)，本題中的 Connect 和 Destroy 均可以用對(duì)應(yīng)的 Cut 和 Link 操作實(shí)現(xiàn)， Query 操作只需要比較兩個(gè)節(jié)點(diǎn)所在有根樹的根節(jié)點(diǎn)是否相同即可?？偣驳臅r(shí)間復(fù)雜度為 O(m logn)，可以在 1s 內(nèi)通過本題的所有數(shù)據(jù)。參考文獻(xiàn)：1D. D. Sleator, R. E. Tarjan, A Data Structure for Dynamic Trees, JournalScien., Vol.26, No.3, June 1983, 362-391.puter and Syst