目錄

• 概念辨析
  • 輔助樹
  • 輕邊和重邊
• 操作介紹
  • access
  • make_root
  • find_root
  • split
  • link
  • cut
• 細節問題
• 代碼

前言:這個算法似乎機房全都會,就我不會了TAT...強行搞了很久,勉強照著別人代碼抄了一遍qwq

這個本人看論文實在看不懂,太菜了啊!!! 只好直接看如何實現...可是實現也看不太懂...

但直到我看到一篇大佬博客!!! point here 是真的講的好,一點都不敷衍.真沒收錢

本篇比較干貨qwq(沒圖啊!!!) 一定要耐住性子學算法!!!

概念辨析

• 但在之前還是要辨析幾個概念:

輔助樹

本人理解就是對于原樹抽象出一個splay 或者說很多棵splay (啥,你告訴我原樹是多叉樹,splay只是一個二叉樹)

其實就是將一個splay劃分成很多部分(每一部分維護原圖中的一條鏈) 然后對于這些部分連輕邊.

(建議先認真看看那些基礎概念) 然后對于一條鏈來說,深度兩兩不同,我們就可以用這個作為splay的鍵值來排序

然后這就可以維護出原樹了... 為什么呢? 因為 雖然父親只能有兩個兒子,但是有很多兒子來認他啊qwq

(就像造樹的時候只要給每個點一個fa就行了) 然后每條鏈又在splay中可以確定他們的先后順序(也就是深度大小)

輕邊和重邊

這個不像樹剖,這個就是隨便給的(根據操作access來改變) 然后重邊存在于splay中的子認父也認 的邊, 也就是維護鏈時候的邊. 然后輕邊,就是只連到父親時子認父不認 的邊,就是一顆splay連到重鏈頂端父親的那條邊,而且一個點只能有一個重邊!

操作介紹

然后就直接介紹操作吧(你還是沒聽懂?那看看別人博客的概念介紹吧qwq)

access

就是拉鏈,就是把一個點到根節點路徑全都變為重邊,且它是這條路徑的一個端點.

如何實現呢qwq... 就是每次把當前這個節點splay到根,然后這個splay的父親認了他這個兒子就行了,

接下來上傳信息... 不斷操作,直到到根 (注意要把他變為樹的一個端點,所以要一開始要將它的兒子認為空的)

access=splay+child+push_up

make_root

使得一個點變為原樹的根,然后這就可以便于維護路徑信息了.

首先先把這個點access到根,之后將這個點splay到當前splay的根,然后再下放一個rev的標記就行了.

這是因為你使當前重鏈的深度完全翻轉了(注意,我們splay是按照深度排序的!!!)

x就變為深度最小的點(即根節點)

make_root=access+splay+rev

find_root

找到原樹的根,這個就易于判斷連通性了(類似于并查集)

又是access到根,然后也是splay到根. (這樣似乎很好維護一些東西,而且更方便去想了)

然后直接一直向左邊走,最下面那個就是根節點了(深度最小, 時間復雜度因為有雙旋所以可以保證)

而且在走左子樹的時候要push_down!! (大佬博客上講的,我還沒被坑過qwq)

find_root=access+splay+go_left_child

split

將原圖中的一條路徑變為一條以它們為端點的重鏈.

假設我們split(x,y). 首先先把make_root(x)便于操作. 然后access(y),拉一條路徑出來.

為了查找信息我們splay(y)到splay的根上去,直接訪問y的信息(中間splay有push_up)

split(x,y)=make_root(x)+access(y)+splay(y)

link

將原圖中的兩個點連一條邊

我們把link(x,y)定義為把x的父親認做y. (其實你互換也是可以的)

如果操作合法,我們只要make_root(x)然后x的父親認做y就行了.

就是讓x變為他所在樹的根就行了qwq.. 不合法的話,就判斷聯通性就行了.

link(x,y)=make_root(x)+father[x]=y

cut

將原圖中的一條邊斷掉

我們同樣把cut(x,y)定義為把原圖中x與其父親y的邊斷掉. (同上互換也是可以的)

這個合法的話,直接把他們中的那條鏈split出來,直接斷掉就行了...

不合法的話,同樣嘗試split出來,如果x的左兒子不是y就不行.

這樣意義就是y在原樹中不是x的父親,不能cut掉.

cut(x,y)=split(x,y)+left_child[y]=fa[x]=0

至此link_cut_tree所有基礎知識已經講完qwq...然后高端操作只能自己做題了...

細節問題

這個lct細節是真的多,一不小心就調不出來了啊!!!

rotate和普通的不同,要判斷是不是當前splay的根!!!!

而且連邊的時候一定要注意順序啊!!!

就是判斷is_root(u)之前不能連u-v的那條邊!!!!

splay那里也是 判斷is_root的時候要注意對象啊,是fa[u]!!!

make_root那里不能先交換一遍!!!直接打標記在那里就行了!!!

(有些人寫法是先交換,再打左右兒子標記,我代碼不同啊!!!)

splay中t要從o開始,然后判斷!is_root(t)而不能從fa[o]開始,這是因為fa[o]可能為\(0\)啊!!!

rotate中是push_up而不是push_down,前面splay中push_down完了啊!!!

代碼

(沒有注釋....湊合對對,這道題是luogu模板)

#include <bits/stdc++.h> #define debug cerr << "Pass" << endl #define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i) #define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i) #define Set(a, v) memset(a, v, sizeof(a)) using namespace std;inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;} inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}inline int read() {int x = 0, fh = 1; char ch = getchar();for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);return x * fh; }void File() { #ifdef zjp_shadowfreopen ("P3690.in", "r", stdin);freopen ("P3690.out", "w", stdout); #endif }const int maxn = 1e6 + 1e3;int val[maxn]; #define ls(u) ch[u][0] #define rs(u) ch[u][1] struct Link_Cut_Tree {int fa[maxn], ch[maxn][2], rev[maxn], xsum[maxn];inline bool is_root(int o) { return o != ls(fa[o]) && o != rs(fa[o]); }inline bool get(int o) { return o == rs(fa[o]); }inline void push_up(int o) { xsum[o] = xsum[ls(o)] ^ xsum[rs(o)] ^ val[o]; }inline void push_down(int o) {if (rev[o]) { swap(ls(o), rs(o)); rev[ls(o)] ^= 1; rev[rs(o)] ^= 1; rev[o] = 0; }}inline void rotate(int v) {int u = fa[v], t = fa[u], d = get(v);fa[ch[u][d] = ch[v][d ^ 1]] = u;fa[v] = t; if (!is_root(u)) ch[t][rs(t) == u] = v;fa[ch[v][d ^ 1] = u] = v;push_up(u); push_up(v);}int sta[maxn], top;inline void splay(int u) {sta[top = 1] = u;for (register int t = u; !is_root(t); t = fa[t]) sta[++ top] = fa[t];while (top) push_down(sta[top --]);for (; !is_root(u); rotate(u)) if (!is_root(fa[u])) rotate(get(u) ^ get(fa[u]) ? u : fa[u]);}inline void access(int o) { for (int t = 0; o; o = fa[t = o]) splay(o), rs(o) = t, push_up(o); }inline void make_root(int o) { access(o); splay(o); rev[o] ^= 1; }inline int find_root(int o) { access(o); splay(o); while (ls(o)) o = ls(o), push_down(o); splay(o); return o; }inline void split(int v, int u) { make_root(v); access(u); splay(u); }inline bool link(int v, int u) { make_root(v); if (find_root(u) == v) return false; fa[v] = u; return true; }inline void cut(int v, int u) { split(v, u); if (ls(u) == v) ls(u) = fa[v] = 0; } } lct;int n, m;int main () {File();n = read(); m = read();For (i, 1, n) val[i] = lct.xsum[i] = read();For (i, 1, m) {int opt = read(), x = read(), y = read();if (!opt) { lct.split(x, y); printf ("%d\n", lct.xsum[y]); } else if (opt == 1) lct.link(x, y);else if (opt == 2) lct.cut(x, y);else { lct.access(x); lct.splay(x); val[x] = y; lct.push_up(x); }}return 0; }

轉載于:https://www.cnblogs.com/zjp-shadow/p/8551548.html

總結

以上是生活随笔為你收集整理的link-cut-tree 简单介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。