Link-Cut Tree

ps：推薦論文《QTREE解法的一些研究》by楊哲。

作用

高效解決動态樹問題。

思想

Link-Cut Tree（簡稱LCT）将樹的邊分為Prefered Edge和普通邊，将點分為Prefered Child和普通點，Prefered Edge和Prefered Child是不斷變化的，且剛開始隻有普通邊和普通點。LCT的核心操作Access(x)：通路x。

假設最後通路了lst節點，對于節點x，如果lst在x的兒子son的子樹中，則son變成x的Prefered Child（原先的Prefered Child變為普通點），連接配接x和son的邊變成Prefered Edge（原先的Prefered Edge變為普通邊，由此可見x至多隻有一個Prefered Child）。特殊的是，lst沒有Prefered Child。那麼顯然通路了lst之後，lst到ro（ro表示lst所在樹的根）之間的邊都變成Prefered Edge了。

對于一條由Prefered Edge連接配接而成的鍊，我們用資料結構（通常用Splay，因為Splay可以友善的分裂和合并）來維護，将鍊自頂向下看做一個序列（dep越小越靠前）用Splay儲存，且這條鍊的Splay的根節點儲存了一個Path Father，表示這條鍊頂端節點的father。要注意，這個關系是單向的，也就是說這條鍊的Splay的根節點的father是Path Father，但Path Father所在Splay和這條鍊的Splay是不連通的。

假設我們已經實作了Access，那麼如何實作Link(x,y)（把y連接配接到x上）和Cut(x,y)（把y從x上斷開）呢？首先我們需要實作一個make_ro(p)，作用是把p變成p所在樹（注意，不是p所在Splay！）的根。代碼如下：

void make_ro(int p) {Access(p);Splay(p);Add_flip(p);}
           

非常簡短，但是好像很費解，我們來看圖：

先通路p，這樣p到ro之間的邊就都變成Prefered Edge了（也就是說p到ro之間的點都在同一個Splay中了），然後把p伸展到p所在Splay的根。由于p是最深的節點，是以其他點均在p的左邊，但是p成為了根節點，這條鍊就被翻轉了，加翻轉标記。完成這三個操作之後，p就成為了新根。

有了make_ro操作，Link和Cut就很簡單了：

void Link(int x,int y) {Access(y);make_ro(y);father[y]=x;}
           

先把y變成根，然後把father[y]給x就行了（不要把son[x][0/1]給y，因為這是單向連接配接）。

void Cut(int x,int y)
{
    make_ro(y);Access(x);Splay(x);
    father[y]=son[x][]=;Pushup(x);
}
           

先把y變成根，然後通路x，通路之後x所在鍊中就隻有x和y兩個節點了，伸展x，則y必定是x的左二子。斷開連接配接，更新x。

然而Access還沒講，其實非常暴力，假設目前處理到p，上次處理了lst。那麼先斷開p與原先Prefered Child之間的連接配接，然後連接配接p和lst，更新p。重複這個過程直到p為空。

void Access(int p)
{
    int lst=;
    while (p)
    {
        Splay(p);son[p][]=lst;Pushup(p);
        //先Splay(p)，這樣son[p][1]就是原先p的Prefered Child的子樹了
        //将son[p][1]給成lst，更新p
        //不用修正father[son[p][1]]，因為p成為了father[son[p][1]]的Path Father
        lst=p;p=father[p]; //繼續處理
    }
}
           

這樣不會逾時嗎？之後再講。

除了Link和Cut，我們還可以實作以下功能：

1.取出x->y的路徑

make_ro(x)，Access(y)，此時x->y的路徑被存在同一棵Splay中。

2.求x和y的LCA

Access(x)，Access(y)，Splay(x)，則LCA=x的Path Father。

特殊：當x沒有Path Father時，LCA=x（因為y跨越了x到ro，是以x沒有Path Father）。

效率

Splay的總效率為 O((n+Q)∗log2(n)) ，但是Access的總效率呢？

Access的效率取決于Prefered Child改變的次數，而Prefered Child改變的次數取決于Prefered Edge改變的次數。Prefered Edge和普通邊不禁讓我們想到了樹鍊剖分-輕重鍊剖分中的重邊和輕邊。根據輕重鍊剖分的定義，我們會發現每次Access，至多有 log2(n) 條普通邊變成了輕的Prefered Edge，也就是說普通邊變成輕的Prefered Edge的總次數為 (n+Q)∗log2(n) 。但是有多少普通邊變成了重的Prefered Edge呢？我們轉化一下，普通邊變成重的Prefered Edge的次數=重的Prefered Edge變成普通邊的次數+n（可能最後全是重的Prefered Edge），而重的Prefered Edge變成普通邊必定意味着一條普通邊變成了輕的Prefered Edge，是以普通邊變成重的Prefered Edge的次數= (n+Q)∗log2(n)+n 。

綜上所述Access的總效率為 O((n+Q)∗log2(n)) ，也就是說LCT的總效率為 O((n+Q)∗log2(n)) 。

ps：然而Splay常數巨大，是以LCT常數巨大……

模闆題

BZOJ2002，題解傳送門。