※ 引述《FRAXIS (喔喔)》之銘言：
: : 推 DJWS: 能不能推薦幾篇centroid/spine decomposition的教學資料? 03/02 08:14
就我有限的理解，我說明一下 spine decomposition ，大家可以討論。
首先考慮一個簡單的問題
輸入： 一條 n 個點的路徑，邊上有權重及長度（可正可負），以及一數字 U 。
輸出： 長度和小於 U 子路徑中，最大的權重和。
這問題跟 maximum sum subarray 很類似，只是差在長度不是 uniform 。
考慮兩種 divide and conquer 演算法。
1. 類似 quick sort
找出路徑的中點 m ，計算出通過 m 滿足條件的最大權重子路徑。
這步會花 O(n lg n)的時間。
然後藉由 m 把路徑分成兩半，分別計算出只在該部份的最大權重子路徑。
總時間會是 O(n lg^2 n)。
2. 類似 merge sort
找出路境的中點 m 。
計算第一個點到 m 的最大權重子路徑，
以及把結尾在 m 的所有路徑按照長度排序。
計算第 m + 1 個點到 n 的最大權重子路徑，
以及把結尾在 m + 1 的所有路徑按照長度排序。
藉由兩半部的路徑，找出通過 m 且滿足條件的 最大權重子路徑。
這步會花 O(n) 時間，總時間是 O(n lg n)。
很明顯方法 1 在 計算通過 m 滿足條件的最大權重子路徑時有些重複計算。
所以方法 2 效率比較好。
然後把輸入從路徑改成樹，思考最大權重子路徑問題。
如果用 centroid decomposition，每次要計算出通過 centroid 且滿足
條件的路徑，需要花 O(n lg n)，這導致最後時間複雜度變成O(n lg^2 n)。
不過其實其中有一些是重複的計算。
這邊我想不太到有沒有什麼方法可以利用子樹的計算來輔助，
主要是一個樹可能會被從不同地方切開，一個子樹可能會跟一堆其他樹相接，
很難維護計算結果。
spine decomposition 不是用一個點把樹切開，而是用一條 path 把
樹切開，切開之後不是兩半，而是一堆子樹，每個子樹與 path 的一個點
相接。
遞迴算出每個子樹中最大權重子路徑，
同時算出在每個子樹中，終點在 path 上的所有路徑按照且長度排序。
然後我們就可以在 path 上用類似方法 2 來 merge 了，
當然這邊 merge 需要有技巧，要保證 merge 的兩個子樹差不多大，
而且 merge 兩個子樹只能花 O(n) 的時間。
不知道有長度下界的時候，能不能也做到O(n lg n)。