Link-Cut-Tree 學習筆記

LCT學習筆記

和樹鏈剖分比較相似，但是它的時間復雜度是 \(O(nlogn)\), 樹鏈剖分是 \(O(nlogn^2)\)

維護一個森林，可以支持以下操作

求聯通兩點 \(x\), \(y\) 的路徑上的所有點的某一求值(eg.\(xor\))
將不聯通的 \(x\), \(y\) 之間增加一條邊
刪除存在的 \((x,y)\) 這條邊
將 \(x\) 的權值改為 \(w\)

定義

每個點最多只有一條邊是連向兒子的實邊，剩下的是虛邊。

維護

用 \(splay\) 維護所有的實邊路徑，用 \(splay\) 中的后繼和前驅來維護原樹中的父子關系
用 \(splay\) 的根節點來維護虛邊

判斷是否是虛邊，就看自己的 \(splay\) 有沒有指向父親所在的 \(splay\) 即可，就是如果 \(u\) 的前驅是\(fa_u\)，但 \(fa_u\) 的后繼不是 \(u\)，則 \((u, fa_u)\) 就是虛邊，反之就是實邊。

操作

就是只有 7 個函數而已

\(access(x)\), 將根節點到 \(x\) 的路徑變成實邊，將其他的與其矛盾的邊變成虛邊
實現：先將 \(x\) 設為這的 \(splay\) 的根節點，然后找到它這棵 \(splay\) 的父節點不妨設為 \(y\),將 \(y\) 設為 \(y\) 所在實鏈的 \(splay\) 的根節點，再將 \(x\) 設為 \(y\) 的后繼就好了(這只要將 \(x\) 的 \(splay\) 插到 \(y\) 的右子樹即可)，此時這條虛邊已經變成了實邊，\(splay\) 的根節點就是 \(y\),以此類推，這條鏈就維護好了
\(makeroot(x)\) 將 \(x\) 設為根節點，還會將 \(x\) 設為 \(x\) 所在的實鏈的 \(splay\) 的根節點。
實現先建立一條 \(x\) 向根節點的實路徑，再將 \(x\) 設為這條實邊的 \(splay\) 的根節點，再將 \((root,x)\) 翻轉。
\(findroot(x)\) 找到 \(x\) 所在樹的根節點，還會將 \(y\) 所在樹的根節點旋轉到 \(y\) 所在 \(splay\) 的根節點。
實現：先將 \(x\) 向 \(root\) 的路徑設為實路徑，再將 \(x\) 設為 \(root\),然后根節點不斷往左走直到不能走，這就是之前的根節點
\(spilt(x,y)\):將 \(x\) 到 \(y\) 的路徑設為實邊路徑
實現：將 \(x\) 變成根節點，然后將 \(y\) 向根節點的路徑設為實邊
\(link(x,y)\):如果 \(x,y\) 不連通，則加入 \(x,y\) 這條邊
實現：是否連通：將 \(x\) 設為這棵樹的根節點，再 \(findroot(y)\) 看一下是不是 \(x\) 即可；連邊：因為 \(makeroot(x)\) 有一個附屬的功能：將 \(x\) 所在的實鏈的 \(splay\) 的根節點設為 \(x\),所以只要讓 \(x\) 的父節點設為 \(y\) 即可。
\(cnt(x,y)\) 如果 \(x, y\) 連通，就將 \((x,y)\) 刪除
實現:是否連通：將 \(x\) 設為這棵樹的根節點，再 \(findroot(y)\) 是不是 \(y\),并且 \(y\) 是 \(x\) 的后繼；刪邊：將 \(x\) 的后繼設為空即可
\(isroot(x)\) 判斷 \(x\) 是否是 \(x\) 所在的 \(splay\) 的根節點
實現:其實就是看一下 \(x\) 有沒有父親即可，如果有，那 \(x\) 一定是他父親的左兒子，或者是右兒子，如果都不是，它就一定是這棵 \(splay\) 的根節點
代碼

void access(int x) 
{
    int z = x;
    for (int y = 0; x; y = x, x = tr[x].p)
    {
        splay(x);
        tr[x].s[1] = y, pushup(x);
    }
    splay(z);
}

void makeroot(int x) 
{
    access(x);
    pushrev(x);
}

int findroot(int x) 
{
    access(x);
    while (tr[x].s[0]) pushdown(x), x = tr[x].s[0];
    splay(x);
    return x;
}

void split(int x, int y) 
{
    makeroot(x);
    access(y);
}

void link(int x, int y)
{
    makeroot(x);
    if (findroot(y) != x) tr[x].p = y;
}

void cut(int x, int y)
{
    makeroot(x);
    if (findroot(y) == x && tr[y].p == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].p = 0;
        pushup(x);
    }
}

維護信息就用 \(splay\) 來維護就好了！

以 \(xor\) 為例， \(splay\) 函數如下：

void pushrev(int x)
{
    swap(tr[x].s[0], tr[x].s[1]);
    tr[x].rev ^= 1;
}

void pushup(int x)
{
    tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}

void pushdown(int x)
{
    if (tr[x].rev)
    {
        pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);
        tr[x].rev = 0;
    }
}

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if (!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x)
{
    int top = 0, r = x;
    stk[ ++ top] = r;
    while (!isroot(r)) stk[ ++ top] = r = tr[r].p;
    while (top) pushdown(stk[top -- ]);
    while (!isroot(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if (!isroot(y))
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}

例題:
2539. 動態樹

按照上面的分析，就可以做了，代碼如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
struct Node
{
    int s[2], p, v;
    int sum, rev;
}tr[N];
int stk[N];

void pushrev(int x)
{
    swap(tr[x].s[0], tr[x].s[1]);
    tr[x].rev ^= 1;
}

void pushup(int x)
{
    tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}

void pushdown(int x)
{
    if (tr[x].rev)
    {
        pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);
        tr[x].rev = 0;
    }
}

bool isroot(int x)
{
    return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
}

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if (!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x)
{
    int top = 0, r = x;
    stk[ ++ top] = r;
    while(!isroot(r)) stk[ ++ top] = r = tr[r].p;
    while(top) pushdown(stk[top -- ]);
    while(!isroot(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if (!isroot(y))
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}

void access(int x) 
{
    int z = x;
    for(int y = 0 ; x ; y = x, x = tr[x].p)
    {
        splay(x);
        tr[x].s[1] = y;
        pushup(x);
    }
    splay(z);
}

void makeroot(int x)
{
    access(x);
    pushrev(x);
}

int findroot(int x)
{
    access(x);
    while (tr[x].s[0]) pushdown(x), x = tr[x].s[0];
    splay(x);
    return x;
}

void split(int x, int y) 
{
    makeroot(x);
    access(y);
}

void link(int x, int y) 
{
    makeroot(x);
    if (findroot(y) != x) tr[x].p = y;
}

void cut(int x, int y) 
{
    makeroot(x);
    if (findroot(y) == x && tr[y].p == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].p = 0;
        pushup(x);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &tr[i].v);
    while(m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if(t == 0)
        {
            split(x, y);
            printf("%d\n", tr[y].sum);
        }
        else if(t == 1) link(x, y);
        else if(t == 2) cut(x, y);
        else
        {
            splay(x);
            tr[x].v = y;
            pushup(x);
        }
    }

    return 0;
}

題單

LCT

posted @ 2025-06-04 15:00 tony0530 閱讀(43) 評論(0) 收藏舉報

刷新頁面返回頂部

tony0530 的小窩

歡迎常來！

Link-Cut-Tree 學習筆記

LCT學習筆記

定義

維護

操作

就是只有 7 個函數而已

題單

公告