[程式] Heavy Light Decomposition (重輕分解；樹鍊剖分)

Heavy Light Decomposition 台灣這邊的翻譯是直譯，所以是叫 "重輕分解"；而中國那邊是採意譯，所以叫 "樹鍊剖分"。這與其說是一種資料結構，倒不如說是一種概念，其基本概念是把一棵樹 (tree) 拆成數條一維陣列，如此一來在這棵樹上的所有查詢 (query)抑或是更新 (update) 都可以在對數時間內完成。詳細的概念可以參考這篇，演算法筆記上的這篇上有列出時間複雜度。

基本概念第一篇已經有用例子詳細解釋了，這邊就不多做說明，會用到這個技巧的場合就以 UVa 12424:Answering Queries on a Tree 來解釋：

題意：給一棵樹，每個節點上都會塗上一種顏色 (最多有 10 種顏色)，並且樹本身的結構不會改變。現在有 2 種可能的操作：

• 改變一個節點的顏色
• 問：從節點 u 到節點 v 唯一的一條路徑上，數量最多的那個顏色其數量是多少？

解析：

基本上這題乍看之下最簡單的操作方法就是件好題目給的數後，要改顏色就直接改：O(1)；要查詢指定路徑上的顏色數量就是直接 DFS 一次就能知道答案。但這題的麻煩點在於其數量級：

• 節點數量 (N) 最多有 10,000 個
• 最多有 10,000 項操作指令

以最糟情況下來看：假設每個操作都是查尋的指令，所以最多會有 10,000 次的查詢次數；每次查詢都需要用一次 DFS，時間複雜度就是節點數量，也就是 O(N)，這兩者加成起來會就會導致所需時間相當龐大。基於查詢次數我們無法控制，因此我們只能想辦法壓低查詢的時間複雜度。另一方面由於節點數量 N 也是頗大，因此我們勢必要將查詢的時間複雜度壓到對數時間內，這就是為什麼這邊需要用上 Heavy Light Decomposition 的原因。

統整一下結論，觀察到下列幾點時可以考慮使用 Heavy Light Decomposition 來：

• 儲存的資料結構是棵樹，並且樹本身的結構是固定而不會變動的
• 查詢樹上資料的頻率極高

最後提一下幾點細節：

1. 經過 Heavy Light Decomposition 後雖然一棵樹會被拆成數條陣列，但是無須每條陣列都建立一個 segment tree，其實只需要一個 segment tree。這個原因在於我們可以把這數條小陣列合併成一個大的一維陣列，然後用這個整併後的一維陣列上建立一個 segment tree 即可。(當然，要每個小陣列都建立自己的 segment tree 也是可以的，這我覺得就自由選擇就好)
2. 利用 LCA 找到任意兩點 u, v 的最低共同祖先 w 後，查詢的路徑被拆成 u->w 以及 v->w。這時務必要注意 w 是否有被重複查詢數次的可能性。同樣以 UVa 12424 這題為例來解釋：這題因為會需要統計路徑上每個顏色的數量，如果有節點被重複查詢就有可能導致統計錯誤。
3. 目前看到的例子雖然都是用 segment tree 當查詢的資料結構，但其實也不一定要用 segment tree，用 binary index tree 這類的資料結構也可。

這次的實作其實花最多的時間是在思考要怎麼把這個概念用 template 作抽象化，就結論而言...其實不太滿意。雖然 tree 的 traversal 可以利用 iterator 簡單解決，但是想不到好方法可以抓出存在 tree 中的資料，最後的替代方案只好變成假定會送到 Heavy Light Decomposition 的樹其節點的基本型態要符合特定結構 (底下實作中的 struct TreeNode)。另一個不滿意的點則是太吃記憶體了，結果導致效能也不甚理想。或許這個方法每次都重新根據目前的資料結構特製化比較妥當。

實作如下，以 UVa 12424 當例子測試：