基本概述

對于原樹進行實鏈剖分，原樹上每一個節點僅向其中一個兒子連實邊，向其他兒子連虛邊。

根據我們維護信息的需求，邊的虛實是可以動態變化的，我們對于每條實邊構成的鏈用一個 DS 維護。而輕邊相當于連接了兩個相鄰的 DS。實鏈剖分之后用平衡樹來維護一條鏈，而由于平衡樹正好是樹的形態，所以我們可以直接將其放入新樹上，用輕邊連接相鄰平衡樹。重鏈剖分之后用線段樹維護，但是線段樹是一個很好的分治結構，卻不是一個好的樹的結構，所以不能直接放到新樹，因此需要用 dfs 序來輔助轉化到線段樹上，因此也導致其多了一個 \(\log\)。

實現

我們需要動態維護這個樹的結構，支持加減邊，動態維護路徑信息。

先定義一些基本數組 \(ch_{u,0/1}\) 表示 \(u\) 節點在平衡樹上的左右兒子，他們左右兒子的 \(fa\) 為 \(u\)。

平衡樹之間的虛邊，滿足認父不認子。也就是某平衡樹的根節點 \(rt\) 的 \(fa_{rt}\) 連向的點正是原樹中平衡樹對應的那一條實鏈最頂端點的父節點，但是由于不在一個平衡樹內，所以父節點的 \(ch\) 中沒有 \(rt\)。注意這個 \(rt\) 在原樹中并不一定是 \(fa_{rt}\) 的兒子，\(fa\) 的兒子應該是這個平衡樹上深度最淺的點。

Splay 部分

\(\rm Nroot\)

Nroot(u) 用來判斷 \(u\) 是不是 Spaly 的根，根據虛邊認父不認子的規則，我們只需要看它父親的左右兒子中是否有它即可。如果有它，就代表它不是 Splay 的根。

bool Nroot(int x){  return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }

\(\rm rotate\)

rotate(x) 代表對于 \(x\) 進行一次 Splay 上的旋轉。

假設目前要旋轉 \(x\)，它的父親和爺爺分別是 \(y\) 和 \(z\)。根據認父不認子，我們通過 \(\rm Nroot\) 來判斷只要 \(y\) 不是平衡樹的根節點，就把 \(z\) 的兒子修改為 \(x\)。如果沒判斷的話會導致不同平衡樹之間認兒子了。

更新很簡單，就是你手畫一下旋轉之后的情況，然后修改三個點的兒子信息，和三個點的父親信息。同時記得判斷節點非空再賦 \(fa\) 的值。最后別忘記 pushup(y)，再 pushup(x)。

void rotate(int x){
	int y=fa[x],z=fa[y],k=get(y,x),w=ch[x][!k];
	if(Nroot(y)) ch[z][get(z,y)]=x;
	ch[x][!k]=y; ch[y][k]=w; 
	if(w) fa[w]=y;
	fa[x]=z; fa[y]=x;
	pushup(y); pushup(x);
}

這里的 get(x,y) 就是在 \(y\) 為 \(x\) 右兒子的時候返回 \(1\)，否則返回 \(0\)。

\(\rm Splay\)

Splay(u) 的時候就需要將 \(u\) 點變成所在平衡樹的根節點。

由于有修改操作，所以我們會維護若干 tag，在平衡樹形態變化的時候需要 pushdown。先將 \(u\) 到所在平衡樹的根路徑自上而下 pushdown。只需要一直跳 \(fa\)，跳到根節點然后從上面開始 pushdown 即可。

只要 \(u\) 不是根就重復執行旋轉。取 \(y,z\) 分別為 \(u\) 的父親和爺爺，當然如果不存在爺爺就可以直接一步 rotate 到位了。如果 \(u,y,z\) 成一字型，我們連轉兩次 \(u\)，否則先轉一次 \(y\)，再轉 \(u\)。

	void splay(int x){
		int y=x,top=0; st[++top]=y;
		for(;Nroot(y);y=fa[y]) st[++top]=fa[y];
		while(top) pushdown(st[top--]);
		while(Nroot(x)){
			y=fa[x]; int z=fa[y];
			if(Nroot(y)) rotate((lc(z)==y)^(lc(y)==x)?x:y);
			rotate(x);
		}
		pushup(x);//(*)
	}

注意：上面打星號的位置，記得上述不斷翻轉結束之后，需要再 pushup 一次。雖然我們 rotate 里面就有 pushup，但是防止 \(u\) 直接是根了，pushdown 導致信息變動，但是進不去 rotate 。

注意：根據上述理論，每一個 Splay 維護的是一條從上到下按在原樹中深度嚴格遞增的路徑，且中序遍歷 Splay 得到的每個點的深度序列嚴格遞增。所以注意 Splay(p) 之后只是保證 \(p\) 為平衡樹的根節點，但并不是原樹的根節點。需要處于最上方的平衡樹且沒有左子樹保證深度最低才是根節點。

動態樹的操作

\(\rm access\)

access(u) 是最重要的操作，將原樹中 \(rt-u\) 路徑上的邊全部變成實邊。

分析一下，\(rt-u\) 的路徑上一定是若干實鏈通過若干條虛邊接在一起。我們需要將虛邊全部變成實邊，也就是連成一條實鏈，同時路徑上其他每個點（包括 \(u\)）的其他邊都要變成輕邊。

如圖是原樹的一個局部情況，我們需要將中間那條虛線邊變輕。同時由于我們是要把 \(rt-u\) 變成實邊，所以只和深度小于 \(u\) 的部分有關系，所以 \(u\) 下方紫色點無用，同理另一個紫色點也要舍棄。舍棄就是直接修改兒子信息就行了，由于認父不認子，我們的 \(fa\) 數組還保留就完美符合要求。

為了把深度大于 \(u\) 的部分都舍棄，我們先 splay(u)，把 \(u\) 變成所在平衡樹的根，然后就可以通過舍棄右子樹來達成目的。對于 \(fa\) 也是同理，直接 \(\rm splay\) 之后舍棄右子樹，同時右子樹連接上 \(u\) 點，這樣子就完成了邊從虛到實的轉化。

	void access(int x){
		for(int y=0;x;y=x,x=fa[x]){
			splay(x); rc(x)=y; pushup(x);
		}
	}

\(\rm makeroot\)

makeroot(u) 換根操作，就是把 \(u\) 變成原樹的根節點。

先 \(\rm access\) 一下打通 \(u\) 和根節點的路徑。這個時候兩者在同一平衡樹內。我們再 \(\rm splay\) 一下，這個時候 \(u\) 成為了最頂端平衡樹的根節點，此時 \(u\) 的左子樹內的點都是深度比 \(u\) 淺的點，而 \(u\) 的右子樹內沒有點，因為 \(u\) 在原樹上就是這條鏈的最深點。因此直接交換左右子樹就可以做到讓 \(u\) 變成最淺點了！這就直接打一個翻轉標記就行了，平衡樹經典操作。

void makeroot(int x){ 
  access(x); splay(x); Reverse(x); 
}

void Reverse(int x){ 
    swap(lc(x),rc(x)); r[x]^=1; 
}

\(\rm findroot\)

findroot(u) 就是找到 \(u\) 所在樹的根節點（一般整個圖是一個森林），類似于并查集的操作。

在 LCT 維護樹，只合并不分離的情況下，我們甚至可以直接用并查集維護聯通性，因為 \(\rm makeroot\) 常數還是比較大的。

還是老套路， \(\rm access +\rm splay\)，這樣子根節點就和 \(u\) 在一個平衡樹內了，根據深度最小，我們不斷跳左兒子即可。同時一定要每一步都 \(\rm pushdown\)。為了保證樹的形態，我們最好最后再把根通過 \(\rm Splay\) 轉回去。

	int findroot(int x){
		access(x); splay(x);
		pushdown(x);
		while(lc(x)) x=lc(x),pushdown(x);
		splay(x); return x;
	}

注意這個是需要一路 pushdown 下去的。

\(\rm split\)

split(u,v) 就是需要提取出路徑 \((u,v)\)，也就是將路徑上的邊都變成實邊。

只需要把 \(u\) 換成根節點之后，對 \(v\) 做一次 \(\rm access\) 就行了。

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

\(\rm link\)

link(u,v) 代表連接邊 \((u,v)\)。

對于保證 \(u,v\) 不聯通情況，直接 makeroot(u)，再 \(fa_u\gets v\)。注意第一步的原因是變根過程中暗含了 \(\rm splay\) 操作，只有平衡樹的根節點才能將 \(fa\) 賦值為實鏈頂的父親。而且為了保證不損失原先 \(fa\) 信息，我們必須將 \(u\) 變成根節點之后，才能賦 \(fa\)。如果直接賦 \(fa\)，就兩個父親了。

對于沒有保證的，我們需要先 makeroot(u)，再看一下 findroot(v)，如果不連通，再對于 \(fa_u\) 賦值為 \(v\)。

	bool link(int x,int y){
		makeroot(x);
		if(findroot(y)==x) return 0;
		fa[x]=y;
		return 1;
	}

\(\rm cut\)

cut(u,v) 就是斷開樹上 \(u,v\) 兩點之間的邊。

如果保證有邊的話，我們直接 split(u,v) 后，\(u,v\) 在同一平衡樹內。此時 \(u\) 必然是 \(v\) 的左兒子，直接雙向斷開即可，需要斷開 \(fa\) 數組和 \(ch\) 數組。

如果不保證 \((u,v)\) 邊存在的話，需要 makeroot(u)，然后判斷一下 findroot(v) 保證兩者在同一聯通塊內，再判斷 \(fa_v\) 看看 \(u,v\) 是否是父子關系，接下來兩個判定單獨拿出來是不成立的，但是由于之前 findroot(v) 的時候，聯通了 \((u,v)\) 并且先把 \(v\) 轉到了平衡樹的根節點，又把 \(u\) 轉回到了平衡樹的根節點，所以這個時候只要 \(fa_v=u\) 的話，\(v\) 是 \(u\) 的右兒子。那么只需要判定 \(v\) 沒有左子樹，如果有左子樹就代表原樹中 \(u,v\) 之間還有別的點，于是最后判定 \(v\) 沒有左子樹就可以了。三條判定如果記不住，就直接 std::map 存一下連的邊就行了。

	bool cut(int x,int y){
		makeroot(x);
		if(findroot(y)!=x||lc(y)||fa[y]!=x) return 0;
		rc(x)=fa[y]=0;
		pushup(x);
		return 1;
	}

應用

簡化版 LCT

P3203 [HNOI2010] 彈飛綿羊

發現每個點只會跳向一個點，符合樹上節點只有一個父親，考慮用 LCT 來維護。我們從每個點向它跳向的點連邊。

本題是一個輕量級版本的 lct，也就是一個只有樹合并分離的 LCT 了。

發現不用換根等等一系列操作。

對于詢問就是查詢 \(rt-x\) 鏈節點個數。不需要用傳統 \(split\) 函數了，因為只需要求到根的信息，直接 \(access+splay\) 解決。

\(link\) 函數，由于保證了 \(x\) 向外連的時候一定是樹根，于是直接 \(splay\)，然后賦值 \(fa\)。

\(cut\) 函數，\(access+splay\) 之后去掉左兒子即可（雙向斷）。同時注意更改的 \(fa\) 信息是 \(ch_{x,0}\) 的而不是 \(x+k_x\) 的。

維護子樹信息

子樹信息分為輕兒子子樹和重兒子子樹，重兒子子樹就是 \(\rm Splay\) 之后的右子樹。

對于每個點記錄所有輕兒子信息和，把 \(u\) 轉成根后，就是平衡樹上右子樹了。
在 access 中 \(ch(x,1)=y\) 的時候 \(O(1)\) 修改。

P4219 [BJOI2014] 大融合

LCT 維護子樹信息模板題。

這里要維護的就是子樹和了。

我們額外維護 \(gs_u\) 代表 \(u\) 的所有輕兒子的信息總和。pushup 內 \(s\) 的累加要帶上 \(gs\)。

\(access\) 往上跳的過程中也要動態調整 \(gs\)。\(link\) 的時候由于加入輕兒子，所以也要修改 \(gs\)，同時注意我們無法一層層往上更新，所以在 link 中更新 \(gs_v\)，必須先 \(\operatorname{makeroot(v)}\)。

每次查詢 \((x,y)\) 就是先斷開 \((x,y)\) 邊，然后各自 \(\operatorname{makeroot}\) 求出兩邊各自的信息乘在一起，然后再連接上 \((x,y)\) 邊。

此外，還有一種做法。根據最終形態建立出森林，然后求出 dfs 序。同時同一個并查集維護樹上聯通塊，我們可以在每次加邊的時候合并。同時大概要維護一個鏈加，求子樹大小。可以用樹狀數組實現樹上差分，子樹大小就是子樹求和了。

加邊刪邊并查集

P2387 [NOI2014] 魔法森林

暴力：枚舉 A 精靈數量 \(a\)，把所有滿足 \(\le a\) 限制的邊按照 \(b\) 升序排序依次加入并查集判斷連通性。

騙分做法：三分 \(a\) ，并查集求 \(b\) 最小值。或者兩層二分 \(a~b\)，然后并查集。但是正確性無法保證。

此時可以像 P5443 [APIO2019] 橋梁，那樣操作分塊+可回退并查集。其實感覺這題更本質一點，那題是針對詢問和修改各有一套做法然后二者平衡一下，似乎詢問操作二者還有點區別。但是這題其實讓我弄懂了詢問和操作本質沒有區別，二者是完全一樣的！映射到橋梁那題中這題里的 \(A\) 就像詢問，\(B\) 就像操作，我們發現其實可以 對枚舉 \(A\) 加入 \(B\)，顯然也可以枚舉 \(B\) 加入 \(A\)，這是完全對稱的！！這也就證明了那題中的詢問和操作的做法其實本質是一樣的本題對邊關于 \(a\) 排序，然后塊內對 \(b\) 排序，把所有之前 \(\le a\) 的邊拿一個指針維護依次加入，問題就完美解決了。

回到 LCT，這是動態樹經典應用：不斷地加邊，判環，取最優者。同時這題還有一個小技巧就是邊化點。定義一條邊 \(i\) 的權值為 \(b_i\)，本題做法就是從小到大枚舉 \(a\), 然后嘗試加入該邊。如果 \(u~v\) 本來就不連通自然是加入成功了，如果二者聯通，那么就在 \(u-v\) 路徑上找到權值最大的點，如果該權值大于目前要加入邊的權值，就把該邊刪除，加入新邊。每次加完邊后判斷一下 \(1-n\) 是否聯通，然后更新答案。這樣整個 LCT 森林維護的就是在當當前約束 \(a\) 之下任意兩點之間的最小 \(b\) 路徑。

P4172 [WC2006] 水管局長

本題條件可以轉化為求最小生成樹上 \(\rm path(x,y)\) 上的最大邊的邊權。

時光倒流，刪邊轉化為加邊。每次加入一條邊如果形成環，我們只需要在環上找最大邊刪掉就行了。用 LCT 維護這個過程，時間復雜度 \(O(n\log n)\)。

綜合題

P8265 [Ynoi Easy Round 2020] TEST_63

集訓的例題，質量挺高的，加深了對于 LCT 的理解。本題不是把 LCT 當工具使用，直接調用各個函數，而是對于其各個函數的實現進行了內部更改。

發現本題這些操作有點像 LCT，于是我們考慮用 LCT 的虛實邊來維護樹上的輕重邊。也就是對應映射一下。那么每個 Splay 上面維護的便是一條重鏈的信息。

考慮將 \(y\) 變成 \(rt\) 的操作，是先 \(\operatorname{access}\) 和 \(\operatorname{splay}\)，再翻轉。一次 \(\operatorname{access}\) 之后 \(y-rt\) 的所有邊都變成了實邊，對應一下也就是所有都變成了重邊，但是顯然不太符合實際情況。我們需要找到那些輕邊在 LCT 中把他們變成虛邊。因為根據輕邊定義 \(sz_u > 2 sz_{son}\)，所以對于每條輕邊必然存在一個 \(k\) 使得 \(sz_u \ge 2^k > sz_{son}\)。可以枚舉 \(k\) 通過 Splay 上二分找到 \(sz_u \ge 2^k > sz_{son}\)，然后直接修。

對于統計重鏈第 \(k\) 大，在每次上述修改虛實邊后一條重鏈會斷成兩段，我們將兩段加入權值線段樹中即可。

同時補充一下，對于上述 \(sz\) 的維護是在 LCT 中維護子樹信息。做法是對于每個點記錄所有輕兒子信息之和 \(gs\) ，改在 \(\operatorname{access}\) 中 \(ch(x,1)=y\) 的時候 \(O(1)\) 修改即可。子樹大小就是 \(gs(u)+s(ch(u,1))+1\)。同時本題規定了在子樹大小相同的時候，選擇下接重鏈上編號更大的那個作為重兒子，于是我們還要記錄最大編號。

然后有一個卡常小技巧就是用兩個優先隊列來代替 set，一個優先隊列負責添加元素，一個優先隊列負責刪元素，這樣子常數小了好多。

下面是對于 LCT 一些傳統的函數內部細節的說明。

在 \(\operatorname{push}\) 中維護的信息 \(sz\) 信息不只是平衡樹上信息了，還要加上其他輕兒子信息 \(gs\)。維護 \(val\) 代表實鏈異或和，也就是重鏈異或和。同時記錄一下該重鏈中最大編號。

void pushup(int u){
   s[u]=1+gs[u]+s[lc]+s[rc];
   Mx[u]=max({Mx[lc],Mx[rc],u});
   val[u]=val[lc]^val[rc]^u;
}

在 \(\operatorname{access}\) 中由于要修改 Splay 中右子樹信息，這一項的修改涉及到了重鏈斷裂成兩個重鏈，同時新的重鏈生成。輕兒子的信息修改。于是我們記錄下一路需要斷開的邊的位置，然后從上到下倒著修改一下。需要用到函數 modify(u,v)表示斷開 \(u\) 原先的右子樹，連上 \(v\)。首先，把原先保存的兩條重鏈權值刪掉。因為重鏈會發生變化。然后維護輕兒子信息，也就是輕兒子的子樹信息和，還有 \(sz\) 的排名保存下來。然后在權值線段樹中加入新產生的兩條重鏈，注意第二條重鏈要在 \(\operatorname{pushup}\) 更新過新的重鏈信息后再加入權值線段樹。當然對于 \(\operatorname{access}\) 造成的重鏈數量變多，我們在 \(\operatorname{link}\)，\(\operatorname{cut}\) 和 \(\operatorname{makeroot}\) 這些調用 \(\operatorname{access}\) 的函數里面再修改，而不是立刻修改。

void modify(int u,int v){
    seg.update(1,0,V,val[u],-1); if(v) 
    seg.update(1,0,V,val[v],-1);
    if(rc) S[u].ins(s[rc],Mx[rc]);
    if(v) S[u].del(s[v],Mx[v]); 
    gs[u]+=s[rc]; gs[u]-=s[v];
    if(rc) seg.update(1,0,V,val[rc],1);
    rc=v; pushup(u); seg.update(1,0,V,val[u],1); 
}

然后 \(\operatorname{cut}\) 的時候，要注意我們先要根據子樹大小看看誰是誰的父親，然后本來要判斷一下 \(v\) 是否是 \(u\) 的輕兒子，但是我們可以通過 access(u) 讓 \(v\) 先變成 \(u\) 的輕兒子，這樣子后面的操作就統一了。

\(\operatorname{link}\) 稍微修改一下，先記錄一下輕兒子信息即可。

\(\operatorname{cut}\)，\(\operatorname{link}\) 和 \(\operatorname{makeroot}\) 函數后面都要跟著一個 change
函數，就是上面那個枚舉 \(k\) 然后 Splay 上二分修改輕兒子的操作。

其余未提及函數均按照原先寫法即可。