天天看點
傳回

Link Cut Tree入門

LCT 是 link cut tree 的簡稱，顧名思義~ 就是樹帶動态的增删邊的操作.

分析

題目背景

動态樹

題目描述

給定 n 個點以及每個點的權值，要你處理接下來的 m 個操作。

操作有四種，操作從 0 到 3 編号。點從 1 到 n 編号。

0 x y 代表詢問從 x 到 y 的路徑上的點的權值的 xor 和。保證 x 到 y 是聯通的。

1 x y 代表連接配接 x 到 y，若 x 到 y 已經聯通則無需連接配接。

2 x y 代表删除邊 (x,y)，不保證邊 (x,y) 存在。

3 x y 代表将點 x 上的權值變成 y。

輸入格式

第一行兩個整數，分别為 n 和 m，代表點數和操作數。

接下來 n 行，每行一個整數，整數在 [1,1e9] 内，代表每個點的權值。

然後有 m 行，每行三個整數，分别代表操作類型和操作所需的量。

輸出格式

對于每一個 0 号操作，你須輸出一行一個整數，表示 x 到 y 的路徑上點權的 xor 和。

輸入輸出樣例

輸入 #1複制

3 3

1

2

3

1 1 2

0 1 2

0 1 1

輸出 #1複制

3

1

輸入 #2複制

5 14

114 514 19 19 810

1 1 2

0 1 2

2 1 2

1 1 2

1 2 3

2 1 3

1 1 3

1 4 5

1 2 5

0 3 5

0 3 4

3 5 233333

0 1 5

0 2 5

輸出 #2複制

624

315

296

232709

232823

說明/提示

【資料範圍】

對于 100% 的資料， 1<=n<=1e5, 1<=m<=3e5

lct是一種動态維護森林結構的算法，它可以讓一個森林支援很多動态的操作——比如連邊（link）、斷邊（cut）、換根（mkrt）、查詢樹鍊資訊....

其實lct就是樹剖的加強版——隻不過樹剖采用線段樹維護樹鍊，是以樹剖能解決的一般是比較偏向靜态樹鍊問題，但是lct使用splay來維護樹鍊資訊, 是以自然的，splay是lct的前置技能~

針對本題的splay的節點的資料結構如下

struct SplayNode
{
    int val, fa, lc, rc, xr, lz; // 目前節點的權值, 父節點, 左孩子, 右孩子, 以目前節點為根的splay子樹的所有節點的異或和, 以目前節點為根的splay子樹的翻轉次數(這是一個懶标記)
};

複制

本題其實樹剖不友善搞的操作就是1+2

樹剖的話，我們學過重鍊剖分和長鍊剖分，而lct操作過程中産生樹剖稱之為實鍊剖分——因為lct操作的過程中會産生一系列的實邊和虛邊.

重鍊剖分中的概念換個名字到實鍊剖分中，那麼我們自然就有 實鍊、實兒子、虛兒子、實邊、虛邊 這些概念 ...

重鍊剖分使用線段樹維護每根重鍊，類比的, lct使用splay維護每條實鍊.

首先我們大緻來看看lct長什麼樣子?

下面圖2就是原樹的樣子, 而圖3就是其一種（注意，僅僅是一種）lct. 換言之, lct就是原樹中的一些連通塊的不交并, 連通塊内部的節點使用圖3中的實線（即實邊）連接配接，但是這些實邊未必是原樹中的邊，而這些連通塊之間通過圖3中的虛線（即虛邊）連接配接在一起，這些虛邊也未必是原樹中的邊. 那麼什麼才叫lct呢?

1. 原樹的每個節點在且僅在一個連通凸塊（即兩個點在其中, 則此兩點之間路徑上的所有點都在其中，下面簡稱連通凸塊為連通塊）中, 即lct是原樹上的一些連通塊的不交并. 2. 連通塊是樹，而且關于在原樹中的深度（下面簡稱深度）構成bst（二叉搜尋樹）,例如圖3中的連通塊CGJH在原樹中的深度分别是2、3、5、4，而該連通塊如果視作樹的話，關于此深度名額恰好是構成bst的.

是以如果學過動态點分治的點分樹的話，就比較好了解lct了——它其實就是原樹的某種重構樹. 連通塊内部點之間的邊就是實鍊剖分中的實邊, 連通塊之間的連邊就是實鍊剖分中的虛邊, emmm, 這種感覺很樹剖~

為什麼連通塊要關于深度形成bst? 因為原樹上的連通塊一定也是樹，現在如果告訴你這棵樹上的點在原樹中的深度形成bst的話，你會發現什麼? 對的，那就是這個連通塊其實在原樹上是一根鍊！也就是前面提到的所謂的實鍊， 是以其實lct就是原樹的實鍊剖分。這就非常自然的将lct和實鍊剖分對應到一起了.

lct中使用splay這種bst來維護上面說的連通塊（實鍊）, 至于為什麼, 後面會說, 現在暫且按住不表.

是以lct就是将原樹剖分成了一棵一棵的splay, 這些splay對應樹上的連通塊，也就是一根一根的實鍊. 因為每條實鍊是由一棵splay維護的， 是以每個節點隻能包含且僅包含在一棵splay中.

是以實邊可以了解為正常的splay中的父子節點存儲方式（即圖1中的藍色、綠色節點就是splay上的一對父子節點），所謂正常指的是父節點的ch[0]或者ch[1]指向子節點， 而子節點的fa指向父節點. 也就是圖1中藍色節點和綠色節點之間的雙向箭頭邊.

虛邊可以了解為splay的一個根節點（圖1中的灰色節點）的fa指針指向一個節點（圖1中的綠色節點），但是這個節點（圖1的綠色節點）在splay上并沒有一個兒子節點是該根節點（圖1中的灰色節點）. 也就是圖1中綠色節點和灰色節點之間的單向箭頭邊.

每棵splay的根節點都有一條虛邊.

Link Cut Tree入門

image

但是注意，不論是實邊還是虛邊，連接配接的兩個節點在同一棵原樹上， 不同點是，實邊連的兩個節點在一棵splay（實鍊）中，虛邊連接配接的兩個節點不在一棵splay（實鍊）中.

下面逐個擊破lct這種資料結構中的各種基本操作

約定: 除非特别說明，下面說将某個點x進行splay意味着将 x 伸展到x所在的splay的根節點位置

首先是lct中最基本且最重要的操作——access操作.

access

access(x): 用途将原樹中從x到原樹根節點的路徑變成一根實鍊. 舉個例子, 下圖是一棵A為根節點的原樹,

Link Cut Tree入門

image

access(N), 表示從要将原樹中的路徑 N->L->I->H->G->C->A變成一條實鍊. 我們假設圖2的lct目前長圖3的樣子. 後面會發現，access(N)操作完成之後該lct的模樣會發生變化.

Link Cut Tree入門

image

步驟:

  1. 将x進行splay，如果是第一次執行步驟1的話, 則将x的右兒子變成虛兒子
  2. 此時x已經是它所在的splay的根節點, 然後找到x的lct中的父節點fa, 則x到fa一定是lct中的虛邊, 然後讓fa進行splay , 然後将fa的右（實）兒子（即ch[1]）設定為x，則自動（因為fa隻能有一個右兒子啊~）就将fa原本的右兒子（如果存在的話）變成虛兒子了. 形象的講，就是兒子(x) 拜托老子（fa）去革命（splay），老子成功上位（splay到根）之後，就扶持兒子做實的右兒子而将原本的實的右兒子踢開變成虛兒子.
  3. 對fa（fa此時已是一棵splay的根節點）的父節點重複上述步驟.

ps: 這裡多說一句, 既然虛兒子本質上并不是真的splay意義下的兒子（即它指向的父節點實際上并不承認有這麼個兒子），是以就沒有所謂的虛左兒子、虛右兒子之說了~

還是以上面圖3為例看一下， 依舊考慮的是access(N)

首先我們對N進行 splay, 也就是将N在O、L、N三個節點組成的splay中進行伸展操作.

Link Cut Tree入門

image

也就是要對下面這棵splay的N節點進行伸展.

Link Cut Tree入門

image

（之字形）splay之後變成

Link Cut Tree入門

image

注意，上面的邊都是實邊. 因為我們是第一次執行步驟1，是以要将N的右兒子O變成虛兒子，也就是讓N.ch[1] = 0 就可以了. 即變成下圖的樣子，注意畫圈的邊從圖6中的雙向箭頭邊（實邊）變成了圖7中的單向箭頭邊（虛邊）

Link Cut Tree入門

image

注意，從上圖的演變我們就能知道為什麼步驟1中說——如果是第一次執行步驟1的話, 則就要将N的右兒子變成虛兒子. 因為N伸展之後，它的右兒子O是深度比它大的，而我們的目的僅僅是構造N到A的實鍊, N顯然是該實鍊的底端節點，注意到實鍊的底端節點的深度是最大的，即N将是這根實鍊上深度最大的節點，是以不能把O也給拉進來. 是以自然要把O變成N的虛兒子.

然後我們繼續, N因為新晉為splay的根節點， 是以自然是其父節點 I 的虛兒子，我們拜托 I 去splay一下，I所在的splay僅僅有 I、K 兩個節點，splay之後顯然 I 做根節點，K是其右兒子（因為 K 深度比 I 大），然後設定I的右兒子為N，則自然的就把I原本的右兒子K踢開變成了虛兒子了, 這一切畫在了圖8中.

Link Cut Tree入門

image

注意，和剛剛說的 為什麼第一次執行步驟1的話就要将右兒子設定成0 道理是一樣的，通過圖8我們就能明白為什麼要将I的右兒子設定成N——因為 N到 I 是虛邊，是以 I 是原樹中N到A所必須經過的節點， 即 I 一定要在N到A的實鍊上出現，而N的深度又是此實鍊上深度最深的——自然比 I 深, 是以 I 的splay意義下的右兒子要設定為N（畢竟splay關于深度形成bst嘛~）.

後面就是圖8步驟的重複了.

Link Cut Tree入門

image

最後，我們伸展H的父節點A, A的右兒子設定為H（A原本的右兒子B就變成了虛兒子）. 就像下圖10

Link Cut Tree入門

image

前面已經說了access(N)的目标是将原樹中的路徑 N->L->I->H->G->C->A 變成實鍊. 而實鍊就是恰好在一棵splay中的（類比于重剖中的一根重鍊就是在一棵線段子樹中的）. 我們剝離出圖10中的這棵splay

Link Cut Tree入門

image

根據lct中的splay是關于節點在原樹中的深度形成bst的事實，深度大小依次為A<C<G<H<I<L<N

然後我們看看圖2中原樹是不是如此? 恰好如此！說明我們access(N)是成功的!

access的僞代碼如下

inline void access(int x)
{
    for(re y = 0; x; x = fa[y = x]) 
    {
        splay(x); // x革命, x可以用圖8中的I了解
        x.rc = y; // 革命成功後扶持y做右兒子,踢開原先的右兒子, y可以用圖8中的N了解
        pushup(x); // splay的結構變了, 肯定要pushup的, 學過線段樹的話很容易了解
    }
}

複制

有了上面的講解, 僞代碼很容易了解.

ps: 這裡多說一句, 通過上面的access操作的圖示，我們就不難發現，如果承認access是lct中重要的基本操作的話（下面就會發現，其他操作大量依賴access），那麼使用splay來維護實鍊（bst）是極為自然的，因為當我們要access(N)的時候，如果N不是它所在的splay的根節點的話，我們就要将N變成它所在splay的根節點才行，為什麼要變成其所在splay的根節點? 因為虛邊是溝通不同splay之間的橋梁，而橋梁的一端必須是splay的根節點啊~ 而這種能将一棵樹中的節點快速（攤還O(logn)）變為根節點的資料結構不就是splay或者fhqtreap了嘛~ 但是網上大佬說 fhqtreap 搞lct 容易被卡常.是以用splay來實作bst就是極為自然的了.

有了access之後，後面的操作就都比較簡單了~

mkrt

mkrt(x) 就是給原樹換根為x.

步驟:

  1. access(x)， 即打通x到原樹根節點rt的路徑為一條實鍊，是以x和rt就在同一棵splay中了（因為實鍊恰好就是一棵splay來維護的嘛~）. 而且因為x在實鍊的最底端，是以x的深度是實鍊中最大的, 是以x就是這棵splay的極右端點.
  2. x 進行splay, 即讓x取代rt， 因為x是該實鍊中的深度最大的點, 是以x取代rt之後是沒有右子樹的（即x沒有實的右兒子）.
  3. 翻轉整棵splay

這裡說的翻轉就是二叉樹翻轉，即翻轉rt為根二叉樹的意味着下面的僞代碼

void dfs(int rt)
{
    if(!rt)
    {
        return;
    }
    swap(rt.lc, rt.rc);
    dfs(rt.lc);
    dfs(rt.rc);
}

複制

為什麼翻轉整棵splay之後就達到了換根的目的呢?

還是畫圖. 圖11進行第二步之後（即N splay 到A的位置）變成

Link Cut Tree入門

image

圖12對應的實鍊就是圖12的splay進行中序周遊的結果 A->C->G->H->I->L->N （深度單調增加），圖12翻轉之後變成（剛好和圖12鏡面對稱）

Link Cut Tree入門

image

對應實鍊變化（就是圖13的splay進行中序周遊的結果）為 N->L->I->H->G->C->A （深度單調增加）. 你看，N從原本實鍊上深度最深的節點變成了深度最淺的節點（原樹的根節點不就是整棵原樹中深度最淺的點嗎?），更确切講，實鍊的順序完全反過來了——這不就實作原樹換根了嗎?

僞代碼就很好了解了

inline void mkrt(int x)
{
    access(x);
    splay(x);
    rev(x);
}

複制

顯然，rev操作要使用splay打懶标記的方法降低複雜度.

findrt

findrt(x) 的目的是找x在森林中的根節點（注意，不是找x所在splay的根節點哈）.

步驟

  1. access(x)
  2. splay(x)
  3. x所在splay的極左節點就是答案ans
  4. （血の教訓）為了防止資料卡鍊, 還要splay(ans)

因為經過步驟1和步驟2, x已經成為其所在splay的根節點, 而且該splay沒有右節點, 而x所在森林中的根節點就是x所在實鍊的頂端, 這是實鍊中深度最小的節點, 是以對應到splay中就是極左節點.

例如圖12中，N所在splay的極左節點就是A，是以A就是N在森林中的根節點. 這是正确的.

僞代碼很好了解

inline int findrt(int x)
{
    access(x);
    splay(x);
    while(x.lc)
    {
        pushdown(x); // 下推懶标記
        x = x.lc; // 一路向左
    }
    splay(x); // 防止資料卡鍊
    return x;
}

複制

關于步驟4的形象說明: 經過步驟1、步驟2，如果x所在splay蛻化成了一根鍊（畢竟splay并不保證絕對的平衡）

Link Cut Tree入門

image

則答案是ans, 如果資料比較毒瘤的一直詢問你findrt(x)的話，則每次你都要經過漫長的上面findrt僞代碼第五行的while循環. 這不就被卡了麼? 是以最後要将ans splay一下. 下次要是還問findrt(x) 的話, 則O(1)時間就可以回答.

link

link(x, y)的目的是x和y之間連邊.

步驟

  1. mkrt(x)
  2. 如果findrt(y) == x, 則x、y在同一棵原樹上, 就别連了. 不然強行連邊的話不就樹中有環了麼?
  3. 将x的lct意義下的父節點置為y，即像圖15這般添加一條虛邊即可（不必連實邊，因為沒有必要的情況下，不需要将x和y放在一根實鍊上）
Link Cut Tree入門

image

僞代碼如下

inline void link(int x,int y)      
{
    mkrt(x);                     
    if(findrt(y) == x)
    {
        return;
    }
    x.fa = y; // 連虛邊, 因為僅僅連的是虛邊, 這條邊在splay中并不實際存在而僅僅是在原樹中實際存在, 是以splay的結構并沒有變化, 是以并不需要pushup來維護splay
}

複制

cut

cut(x, y) 目的是斷掉x和y之間的連邊（實邊），這是link(x, y)的逆操作. 同樣要注意資料的合法性.

步驟:

  1. mkrt(x)
  2. 如果findrt(y) != x || y.fa != x || y.ch[0] != 0 那麼直接return掉
  3. 斷實邊. 即将x.ch[1] = y.fa = 0
  4. pushup(x)

其中第二步是什麼道理呢? findrt(y) != x 意味着x和y根本就不在一棵原樹上，那自然是不能cut的. 那自然要return 掉, 是以我們現在假設findtr(y) == x成立. 然後我們注意到 findrt(y) 的最後一步是将 findrt(y) 的結果，也就是x splay到根（注意，經過findrt(y), 确切講是經過 findrt 的第一步access之後，y和x已經在一條實鍊上了, 即已經在一棵splay中了）, 而x是原樹的根節點啊~ 是以深度是最小的, 是以x被splay到根之後它隻會有右節點. 茲麻裡, y在x的右子樹中, 那麼什麼情況下x和y之間不能進行cut呢? 無非就是下面兩種使得x和y在原樹上不相鄰（不相鄰自然不能cut）的情況

Link Cut Tree入門

image

情況1對應的就是 y.fa != x 情況2對應的就是 y.ch[0] != 0

僞代碼就很好懂了

inline void cut(int x,int y) 
{
    mkrt(x); 
    if(findrt(y) ^ x || y.fa ^ x || y.ch[0]) 
    {
        return;
    }
    y.fa = x.ch[1] = 0; 
    pushup(x); // 因為x和y斷了實邊, splay的結構發生了變化, 是以要pushup維護splay
}

複制

split

split(x, y) 的目的是把 x 到 y的路徑（是以前提肯定是x和y在同一棵樹中, 題目的輸入也保證這一點）變成一根實鍊.

步驟

  1. mkrt(x), 即先讓x、y中的一個點變成所在樹的根節點, 友善後續操作.
  2. access(y)，x和y之間的路徑就變成了一根實鍊了，而且這根實鍊恰好通過一棵splay維護起來了.
  3. splay(y)，因為上一步的access(y)使得y成為xy之間的實鍊上深度最大的點, 是以将y splay到根節點，則新的splay就沒有右兒子, 這樣友善操作. 因為你想詢問這條實鍊上的屬性隻需要通路y節點的屬性就可以了.

僞代碼就很好懂了

inline void split(int x,int y)
{
    mkrt(x);
    access(y);
    splay(y);
}

複制

至此, lct這種資料結構的基本操作都講完了. 下面開始切代碼.

//#include "stdafx.h"
//#define LOCAL
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define re register int
#define ilv inline void
#define ili inline int
#define ilc inline char
#define swp(x, y) x^=y^=x^=y
namespace fastio
{
    const int BUF = 1 << 21;
    char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;
    int pw;

    ilc gc()
    {
        if (pr1 == pr2)
        {
            pr1 = fr;
            pr2 = fr + fread(pr1, 1, BUF, stdin);
            if (pr1 == pr2)
            {
                return EOF;
            }
        }
        return *pr1++;
    }

    ilv flush()
    {
        fwrite(fw, 1, pw, stdout);
        pw = 0;
    }

    ilv pc(char c)
    {
        if (pw >= BUF)
        {
            flush();
        }
        fw[pw++] = c;
    }


    ilv read(int &x)
    {
        x = 0;
        char c = gc();
        while(!isdigit(c))
        {
            c = gc();
        }
        while(isdigit(c))
        {
            x = (x << 3) + (x << 1) +(c ^ 48);
            c = gc();
        }
    }

    ilv write(int x)
    {
        if (x > 9)
        {
            write(x / 10);
        }
        pc(x % 10 + 48);
    }

    ilv writeln(int x)
    {
        write(x);
        pc(10);
    }

} using namespace fastio;
const int maxn = 1e5+5;
int n, m;
struct SplayNode
{
    int val, fa, ch[2], xr, lz;
} sp[maxn];

ili ntrt(int cur)
{
    int fa = sp[cur].fa;
    return sp[fa].ch[0] == cur || sp[fa].ch[1] == cur;
}

ili isrc(int cur, int fa)
{
    return sp[fa].ch[1] == cur;
}

ilv pushup(int cur)
{
    int lc = sp[cur].ch[0], rc = sp[cur].ch[1];
    sp[cur].xr = sp[lc].xr ^ sp[cur].val ^ sp[rc].xr;
}

ilv pushdown(int cur)
{
    int &lc = sp[cur].ch[0], &rc = sp[cur].ch[1];
    if (sp[cur].lz)
    {
        if (lc)
        {
            sp[lc].lz ^= 1;
        }
        if (rc)
        {
            sp[rc].lz ^= 1;
        }
        swp(lc, rc);
        sp[cur].lz = 0;
    }
}

ilv rotate(int cur)
{
    int fa = sp[cur].fa;
    int ga = sp[fa].fa;
    int t = isrc(cur, fa);
    int k = isrc(fa, ga);
    int chd = sp[cur].ch[t ^ 1];
    sp[fa].ch[t] = chd;
    if (chd)
    {
        sp[chd].fa = fa;
    }
    if (ntrt(fa))
    {
        sp[ga].ch[k] = cur;
    }
    sp[cur].fa = ga;
    sp[fa].fa = cur;
    sp[cur].ch[t ^ 1] = fa;
    pushup(fa);
    pushup(cur);
}

void pushdownall(int cur)
{
    if (ntrt(cur))
    {
        pushdownall(sp[cur].fa);
    }
    pushdown(cur);
}

ilv splay(int cur)
{
    pushdownall(cur);
    while(ntrt(cur))
    {
        int fa = sp[cur].fa;
        int ga = sp[fa].fa;
        int t = isrc(fa, ga);
        int k = isrc(cur, fa);
        if (ntrt(fa))
        {
            t ^ k ? rotate(cur) : rotate(fa);
        }
        rotate(cur);
    }
}

ilv access(int x)
{
    for (re y = 0; x; x = sp[y = x].fa)
    {
        splay(x);
        sp[x].ch[1] = y;
        pushup(x);
    }
}

ilv mkrt(int x)
{
    access(x);
    splay(x);
    sp[x].lz ^= 1;
}

ili findrt(int x)
{
    access(x);
    splay(x);
    while(sp[x].ch[0])
    {
        pushdown(x);
        x = sp[x].ch[0];
    }
    splay(x);
    return x;
}

ilv link(int x, int y)
{
    mkrt(x);
    if (findrt(y) == x)
    {
        return;
    }
    sp[x].fa = y;
}

ilv cut(int x,int y)
{
    mkrt(x);
    if (findrt(y) ^ x || sp[y].fa ^ x  || sp[y].ch[0])
    {
        return;
    }
    sp[y].fa = sp[x].ch[1] = 0;
    pushup(x);
}

ilv split(int x, int y)
{
    mkrt(x);
    access(y);
    splay(y);
}

signed main()
{
#ifdef LOCAL
    freopen("d:\\data.in", "r", stdin);
//  freopen("d:\\my.out", "w", stdout);
#endif
    read(n), read(m);
    for (re i = 1; i <= n; i++)
    {
        read(sp[i].val);
    }
    int op, x, y;
    while(m--)
    {
        read(op), read(x), read(y);
        switch(op)
        {
        case 0:
            split(x, y);
            writeln(sp[y].xr);
            break;
        case 1:
            link(x, y);
            break;
        case 2:
            cut(x, y);
            break;
        case 3:
            splay(x);
            sp[x].val = y;
            break;
        default:
            break;
        }
    }
    flush();
    return 0;
}

複制

ac情況

所屬題目

P3690 【模闆】Link Cut Tree （動态樹）

評測狀态

Accepted

評測分數

100

程式設計語言

C++

代碼長度

3.72KB

用時

769ms

記憶體

10.06MB

小結

本文學習了 lct 這種處理動态樹的資料結構，但是通過上面的學習，我們發現lct有一個東西處理不了——維護子樹資訊，因為我們知道，比如重鍊剖分可以處理子樹（因為子樹就在一棵線段子樹上）或者樹鍊資訊，lct可以處理樹鍊上的資訊（本題就是這樣）但是維護不了子樹上的資訊~ 這時候就需要更進階的資料結構——Top Tree.

後面再學習Top Tree~ 事實上，樹剖除了删邊操作之外都能搞（加邊就是樹剖+并查集）而且常數比lct小很多（因為lct的大量依賴splay操作，是以lct的常數比較大），是以樹剖性能比lct高而且好寫~ 是以能用樹剖就用樹剖哈~

上一篇: 行業分享-5G+智能電網承載需求分析5G+智能電網
下一篇: 【Pre-Training】XLNet：預訓練最強，舍我其誰1.Introduction2.XLNet3.Experiments4.Conclusion5.Reference