動態圖演算法 (上)

02-04

一鴿就是一個月啊……最近事情也挺多的再加上看了一段時間的線代和ML，也沒怎麼看paper了。<del>暫且用這個墊著吧。</del>

原文：G. N. Frederickson. Data structures for on-line updating of minimum span-

ning trees, with applications. SIAM J. Comput., 14:781 - 798, 1985.

看著看著paper發現又看到冬令營講過的內容了，偷了個懶（然而寫起來還是累死了）就先說這個吧qaq。

這裡考慮三個問題：連通性，最小生成樹 (MST) 和雙連通性。

支持的操作有：加邊，刪邊（MST 里還有修改邊權）。

離線部分

連通性可以維護以刪除時間為權值的最大生成樹。 $O(nlog n)$

MST我還沒想到什麼更好的做法，線段樹分治+LCT應該可以。 $O(nlog^2 n)$

（話說當時看了好久的嚴格 $O(log n)$ 的LCT一直沒有明白，什麼時候我再去看看吧）

雙連通性應該可以分治+並查集。 $O(nlog^2n)$

在線 - 連通性

我們考慮還是給邊一個權值（為了不和MST中的權值混淆，下稱其為等級），繼續維護最大生成森林。

我們令 $T_w$ 是生成森林中等級 $geqslant w$ 的邊形成的森林。

插入一條新邊時令其等級為0。

刪除非樹邊是不會有問題的，刪除樹邊的時候我們需要尋找一條非樹邊來替換。

我們考慮暴力枚舉，當我們刪除一條等級為 $w$ 的邊 $(x,y)$ 時，就枚舉 $w-1$ 以下的等級，試圖替換這條邊。

假設枚舉到等級 $i$ ，我們在 $T_i$ 中考慮，令刪除邊後樹中 $x$ 所在的連通塊為 $C_x$ ， $y$ 所在的連通塊為 $C_y$ ，設 $|C_x|leqslant|C_y|$ 。

我們並沒有什麼很好的方法，所以只能暴力枚舉 $C_x$ 的每條邊，由於只有 $C_x$ 和 $C_y$ 的連通性發生了改變，所以這些邊應該要麼是 $C_x$ 內部的，要麼是 $C_x$ 連向 $C_y$ 的。只要找到一條屬於後者的邊我們就完成任務可以退掉，遇到前者我們就把它的等級+1。

這樣的話時間複雜度就是 $O(nr)$ ，其中 $r$ 是最大等級。

我們來對我們的演算法進行一些觀察，來試圖證明 $r=O(log n)$ 。

我們不難發現，在 $T_{i+1}$ 中， $C_x$ 必然是不會和其他連通塊相連的，因為 $T_{i+1}subset T_i$ ，於是我們每次實際上都把 $T_i$ 中的一個連通塊的一半搬到了 $T_{i+1}$ 去，從而證明了 $T_i$ 的連通塊大小不會超過 $n/2^i$ ，從而證明了 $r=O(log n)$ 。

每一層的 $T_i$ 可以用LCT維護，複雜度就是 $O(nlog^2 n)$ 。

在線 - MST(sqrt m)

現在我們遇到非常棘手的問題了，維護MST是比維護連通性難很多的問題，不過我們可以退而求其次，試圖在根號的時間內解決，也就是對MST分塊。

我們面臨的主要問題是：怎麼分塊，link/cut的時候怎麼保證分塊的性質，怎麼處理非樹邊替換樹邊。

我們一個個問題來看，首先是如何分塊，我們顯然是不能直接分塊的，於是我們可以用經典的左兒子右兄弟來處理這個圖使其度數至多為3，然後就可以分成 $O(m/z)$ 塊，每塊的大小是 $O(z)$ 的。

Link/cut的時候保證性質也比較容易，因為我們是對大小分塊的，只需要保證塊大小是O(z)的即可，因此直接暴力dfs整個塊進行merge/split即可。

現在我們遇到了最大的問題，怎麼處理非樹邊替換樹邊的問題，暴力的話要暴力枚舉用來替換的邊 $(x,y)$ 的端點所在的塊。不暴力的做法的話，我們可以考慮對每個塊用數據結構來維護它連到每個其他塊的邊的最小值。我們可能會進行的操作有：link/cut/詢問一個連通塊內的點權最小值(我們可以先cut掉要替換的樹邊，然後直接對另一個連通塊查詢)/修改點權。這個看起來可以用Top Tree來做，於是這樣我們應該可以大概得到一個 $O(msqrt{m}log m)$ 左右的做法。

因為我們加入了額外的數據結構，於是我們來回顧merge和split的過程，我們注意到一個點的度數至多為3，所以我們其實還是可以暴力重建整個塊的數據結構(Top Tree)。

為了不用 Top Tree 這種既複雜也慢的數據結構，也為了把那個log去掉，我們試著取尋找能替代 Top Tree 的數據結構，畢竟我們只需要詢問整個連通塊的點權最小值而不是子樹的。我們可以繼續考慮我們之前的分塊，因為我們之前實際上是一棵 $sqrt{n}$ 叉樹，我們能不能把它改成類似2叉樹(實際上叫 Topology Tree ，下簡稱TT)的形式呢？我們可以取 $z=2$ ，分塊以後把每個塊縮成一個點，這樣每次都會把點數折半，從而就使深度變成了 $O(log n)$ ，看起來問題就很順利的解決了。

但等等！真的解決了么？我們需要保證的最大問題：度數至多為3這一點並沒有被保證。或許我們可以把z取到4然後再故技重施把度數再變回3，但那樣的話可能merge/split操作會變得令人非常痛苦（雖然我認為最終的解決方案還是很令人痛苦），而且也有失優雅。事實上我們有更好的做法：我們可以簡單的在之前的限制中加入度數不超過3的限制，就可以輕鬆（真的么）的解決問題。分塊的代碼如下：

def findcluster(x):ntclust = [v]ntfor v in child[x]:nttclust.append(findcluster(v))nntif len(clust) < Z && degree(clust) < 3:nttreturn clustntelse:nttprint clustnttreturn []n

我們分析一下塊的數量，令度數為 $i$ 的塊數為 $C_i$ 。由於度數不為 $3$ 的塊的大小一定達到了 $z$ ，因此 $C_1+C_2=O(m/z)$ 。然後我們可以列出方程：

$begin{equation} left{ begin{aligned} C_1+C_2+C_3&=V C_1+2C_2+3C_3&=2V-2 end{aligned} right. end{equation}$

就可以簡單的解得 $C_1=C_3+2$ ，從而證明了塊數是 $O(m/z)$ 的。（註：在這裡有一件事情要說明，圖中的每個點度數不超過3，樹中的每個塊度數不超過3，但是如果在圖中看每個塊，度數是沒有保證的，這也是我們不能直接用這個方法分塊暴力的原因）

儘管我們得到了可以進一步剖分的做法，然而由於我們在分塊的時候對度數也加入了限制，merge/split的過程就會變得更加複雜。為了最後的做法，我們必須硬著頭皮來分析。

Merge的時候，我們要把一棵TT插到另一棵下面，會使得某個TT節點的度數增加，從而整個到根路徑上的點的度數都可能會增加，因此某些塊的度數會從3變成4。不加證明的給出結論（由於點數較少應該可以分類討論），我們可以把這個塊拆成兩個合法的新塊，從而把問題丟給它的父親。拆成新塊可以重新用函數計算。（例子參見下圖）

上面這麼丑的圖怎麼可能是我畫的哼

Split的時候，我們按照那條邊把包含這條邊的塊切開，然後對於不合法的情況像Merge一樣處理掉即可。（例子參見下圖）

有了新的數據結構，link(合併兩棵樹)/cut(分裂開一棵樹)/查詢整個連通塊的最小點權/修改點權(像線段樹一樣維護最小值)都能在 $O(log n)$ 的時間內解決了，而建樹的複雜度是 $O(n)$ 的（和線段樹是一樣的），我們就把複雜度推到了 $O(msqrt{mlog m})$ 上，然而我們還是沒有去掉那個 log 。

我們考慮直接維護塊之間的最小邊，還是先對 $z$ 分塊，然後對縮點之後的樹建TT。對於兩個深度相同的 TT 節點 $u,v$ ，我們開一個2D TT節點 $D_{u,v}$ 來維護 $u$ 與 $v$ 之間的最小邊， $D_{u,v}$ 的子節點是 ${D_{u,v}|uin son_u,vin son_v}$ 。

當 TT 的形態產生變化時，我們也要修改對應的 2D TT 。根據我們之前的分析， TT 的變化都是根到某個節點 $x$ 的變化。那麼我們需要修改的點數就是 $sum_{k=1}^{dep_x}(text{Number of TT Nodes with depth $k$})leqslant text{Number of all TT Nodes}=O(m/k)$ 詢問時即是詢問 TT 中兩個節點 $u$ 和 $v$ 的最小邊，令 $u$ 是深度較大的點，暴力枚舉 $v$ 的子樹中的與 $u$ 深度相同的點 $r$ ，取 $min{val(D_{u,r})}$ 即可，複雜度 $O(m/z)$ 。最後令 $z=sqrt{n}$ 即可。

另：感覺直接發原論文的截圖好像不太對勁……我自己待會去畫一個好了……