輸入：一個 n 個頂點的樹 T，每一個頂點 v 有一個整數權重 w(v)，及一整數 k。
輸出：一條 T 上的路徑（任意起點終點），其路徑上頂點權重的總和為 k 。
這問題應該可以用O(n lg n)解出來，只是需要用centroid decomposition
或是 spine decomposition。
有沒有比較好實作又有效率（o(n^2)）的解法？
另外我想問，有沒有辦法把這個問題轉化成一個樹，其權重是在邊上而不是在
頂點上。因為大部分的文獻都是考慮權重在邊上的問題。
這是在 careercup 上看到的
http://www.careercup.com/question?id=2971

感覺枚舉每個起點BFS就好

但是要怎麼做成o(n^2)?

能不能推薦幾篇centroid/spine decomposition的教學資料?

考慮一條路徑是否通過節點 v，每次找樹的重心，假設存有通過重心的路徑為 k，反之沒有則查找子樹？這樣有可可能比較快嗎？

你說的方法就類似 centroid decomposition 了

路徑先從lca切兩段 兩段分開處理 針對一段路徑 每次找樹的重心 路徑長度只剩下不到一半 所以是log級別^^^^^^^^不是路徑長度 是剩下的節點數量等等 centroid decomposition如何計算一條路徑的權重?http://www.ugrad.cs.ubc.ca/~cs490/2014W2/pdf/jason.pdf