Borůvka 樹分治（二）：King's 轉化

King's 轉化（King's Reduction）將我們前一篇提到的區間最大值的問題，變成一個樹上路徑最大值問題（Tree Path Maximum）。我們接續前一篇所舉的例子：

在這個例子中，若我們將每一次 Borůvka 步驟所獲得的連通元件具體定義為樹上的一個點，並且與連通元件內的所有點都連起來（並且給予適當的權重），就會形成以下的樹 \(B\)。

大家不妨可以檢驗看看，隨意挑選一個區間，這個區間的起點和終點會對應到該樹上的兩片葉子。而區間內數值的最大值，會恰好等於樹 \(B\) 中的兩個點之間路徑上的最大權重。值得一提的是，在樹 \(B\) 當中的這條路徑，不見得恰好包含原本區間內的所有數值，它可能會多一些數值、也可能會少一些數值。但這個 King's 轉化厲害的地方是，這條路徑總是包含最大值、而且這個轉化也適用於輸入是一棵樹的情形。

現在讓我們來仔細定義這棵樹。對於一個輸入的樹 \(T=(V, E)\)（上述例子中，這棵樹是一條路徑），我們先執行一連串的 Borůvka 步驟。 並且我們定義 \(t_{i, j}\) 為第 \(i\) 次 Borůvka 步驟找出的第 \(j\) 個連通元件。 為了方便起見我們將原本樹 \(T\) 的點集合 \(V\) 寫作 \(V=\{t_{0, j}\}\)。 定義樹 \(B\) 如下：

• \(B\) 的所有節點，為所有連通元件所形的集合 \(\{t_{i, j}\}\)。樹根為 \(t_{\ell, 0}\)，而 \(\ell\le \log \vert V\vert \) 為 Borůvka 步驟進行的總次數。
• 樹 \(T\) 的每一個節點 \(t_{0, j}\)，對應到樹 \(B\) 的一片葉子。
• 對於所有連通元件 \(t_{i, j}\)，它與所有屬於該連通元件的前一層節點 \(t_{i-1, k}\) 都建立一條邊，且權重定義為 \(T\) 上面由 \(t_{i-1, k}\) 往外連所有邊中權重最小值。

性質 MST.14

上述定義之樹 \(B\) 的確是一棵樹，而且每一個內部節點至少有兩個以上的子節點。

性質 MST.14 的證明

由於 \(T\) 是連通的，因此其定義出來的樹 \(B\) 的確是一棵樹。此外，由於每一次的 Borůvka 步驟，會將每一個連通元件與至少另一個連通元件合併。因此每個 \(B\) 上面的第 \(i\) 層的內部節點 \(t_{i, j}\) 至少有兩個位於第 \(i-1\) 層的鄰居。

對於所有葉子深度都相同、並且每個內部節點都有兩個或更多的子節點的樹，我們稱為完滿分叉樹（Full Branching Tree）。這樣的性質保證了建構出來的 \(B\) 不會太大。

係理 MST.15 (證明略)

假設輸入之樹 \(T\) 節點數有 \(n\) 個。那麼樹 \(B\) 的節點數不超過 \(2n-1\)。

接著我們證明這個定義出來的樹 \(B\) 上面關於區間最大值的最重要性質：

引理 MST.16 [1]

對於給定的兩個點 \(u:=t_{0, j}\) 以及 \(v:=t_{0, k}\)，\(u\) 和 \(v\) 之間在 \(T\) 上路徑 \(u\leadsto_T v\) 的最大邊權，總是等於這兩點在 \(B\) 上路徑 \(u\leadsto_B v\) 的最大邊權。

引理 MST.16 的證明

對於每條邊 \(e\) 我們用 \(w(e)\) 來表達它的權重。首先，我們證明對於任何一條 \(B\) 上面路徑的邊 \(e\in u\leadsto_B v\)，都能找得到一條 \(T\) 上面路徑的邊 \(e'\in u\leadsto_T v\) 使得 \(w(e') \ge w(e)\)。 令 \(e=(t_{i-1, x}, t_{i, y})\)，由註標可知，\(t_{i-1, x}\) 在 \(T\) 上代表的是一個連通元件，而在第 \(i\) 次 Borůvka 步驟執行時，\(t_{i-1, x}\) 選擇了邊權重為 \(w(e)\) 的邊，這條邊是所有 \(t_{i-1, x}\) 外連的邊中權重最小者。

此外，由於 \(e\) 是 \(e\in u\leadsto_B v\) 的一條邊，這蘊含了 \(u\) 與 \(v\) 恰有一個點在 \(t_{i-1, x}\) 所在的連通元件裡面、另一個點在外面。因此，在 \(T\) 的路徑 \(u\leadsto_T v\) 上面存在一條邊 \(e'\) 是從 \(t_{i-1, x}\) 跨出去的，從前述對 \(w(e)\) 的推論可知此時必定有 \(w(e') \ge w(e)\)。

接下來，我們證明在 \(u\leadsto_T v\) 這條路徑中的最重邊 \(e'=(a, b)\)，其權重值必定出現在 \(u\leadsto_B v\) 上面。不妨假設這個權重 \(w(e')\) 是路徑上唯一的。此時我們宣稱，在某一次 Borůvka 步驟執行時，當 \(a\) (或 \(b\)) 所在的連通元件 \(t_{i, j}\) 選擇了 \(e'\) 這條邊作為外連邊進行合併的時候，該連通元件必定包含 \(u\) 或 \(v\) 至少一個點。證明如下：若不然，當 \(a\) (或 \(b\)) 所在的連通元件選擇了 \(e'\) 這條邊作為外連邊進行合併時，\(u\leadsto_T v\) 這條路徑上至少有兩條不同邊跨越 \(t_{i, j}\) 這個連通元件。然而，\(e'\) 是比較重的那條，根據 Borůvka 步驟的描述 \(t_{i, j}\) 是不可能選擇 \(e'\) 合併的，與 \(t_{i, j}\) 挑選 \(e'\) 這個假設矛盾。

另一方面，\(t_{i, j}\) 挑選 \(e'\) 合併時，\(u\) 或 \(v\) 也剛好有一個點不在其中：若不然，代表有另一條路連接 \(u\) 到 \(v\)，與 \(T\) 為一棵樹的假設矛盾。既然 \(t_{i, j}\) 挑選 \(e'\) 合併時，\(u\) 或 \(v\) 恰好有一個點在其中，這代表 \((t_{i, j}, t_{i+1, j'})\) 這條邊出現在 \(u\leadsto_B v\) 這條路徑上，而且其權重恰好等於 \(w(e')\)，得證。

於是乎，任何經過 King's 轉化的樹，任兩點之間的距離都不超過 \(\log n\)（根據最小共同祖先 LCA 的位置，只要往上爬不超過 \(\ell\) 層再往下走就能走到另一點啦。）因此，上述轉化不只是解決了區間最大值問題，還可以解決樹上路徑最大值問題：

(靜態離線) 樹上路徑最大值問題 Tree Path Maximum

給定一棵有邊權的樹 \(T\)，以及一系列預先給定好的詢問 \(\{(u_i, v_i)\}_{i=1}^m\)。對於每一個詢問，請回答 \(T\) 上面連接 \(u_i\) 與 \(v_i\) 的這條唯一路徑上，所有邊權重的最大值。

定理 MST.17

存在一個 \(O(n+m\log n)\) 時間複雜度的演算法，解決樹上路徑最大值問題。

定理 MST.17 的證明

我們可以先花線性時間 \(O(n)\) 對 \(T\) 跑一次 Borůvka 演算法，並且算出 King's 轉化後的樹 \(B\)。對於每一筆詢問 \((u_i, v_i)\)，同時讓 \(u_i\) 和 \(v_i\) 在 \(B\) 中往上爬，並且記錄中間經過的所有邊權重的最大值。根據引理 MST.16，途中經過得最大值，就會是 \(T\) 上面 \(u_i\) 到 \(v_i\) 路徑上的最大權重，因此答案是正確的。往上爬所需要的時間是 \(O(\ell) = O(\log n)\)，因此整體時間複雜度是 \(O(n+m\log n)\)。

從幾乎線性到線性

從定理 MST.17 的證明看來，在完滿分叉樹上面解決樹上路徑最大值問題，我們只是很平鋪直敘地應用 King's 轉化，並平鋪直敘地暴力找出每條路徑上的最大邊權。而事實上，我們能夠利用更多的單調性質，並且利用巧妙的位元運算（bit tricks）設計出更快速的演算法！

在下一篇文章中，我們將介紹 Full Branching Tree 上面解決靜態離線樹上路徑最大值問題的 Hagerup 演算法² 與其核心的 Komlós 分析³。

為什麼標題叫做樹分治？

樹分治是一種將形狀偏頗的樹轉化成一棵平衡樹的一類技巧。 根據實際需求，在設計資料結構（和演算法）時不一定要實際將轉化的平衡樹算出來，重點是能將長鏈的部分以對數時間方法走訪即可。 這類技巧包含常見的樹鏈剖分 Heavy-Light Decomposition、啟發式合併(知乎)、輕重樹剖分 DSU on Tree、最平衡樹分治問題 POI 11th Cave。 它們的核心概念是相同的，但是根據題目需求，建構出來的資料結構或演算法也長得不太一樣，今天我們討論的 King's 轉化就是一類樹分治的演算法。

備註

在維多利亞大學（University of Victoria）任職的 Valerie King，於 1995 年發表了一篇驗證最小生成樹的線性時間演算法。該演算法中最重要的一步——也就是 King's 轉化——是將樹上路徑最大值問題（Tree Path Maximum）轉化成完滿分叉樹（Full Branching Tree）上面的路徑最大值問題。