作者FRAXIS (喔喔)
看板Prob_Solve
標題[問題] 樹上路徑和為 k
時間Mon Mar 2 00:24:46 2015
輸入：一個 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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1425227089.A.374.html
1F：推 fenzhang: 感覺枚舉每個起點BFS就好 03/02 02:10
2F：→ FRAXIS: 但是要怎麼做成o(n^2)? 03/02 02:19
3F：推 DJWS: 能不能推薦幾篇centroid/spine decomposition的教學資料? 03/02 08:14
4F：推 Morris1028: 考慮一條路徑是否通過節點 v，每次找樹的重心，假設存 03/02 15:05
5F：→ Morris1028: 有通過重心的路徑為 k，反之沒有則查找子樹？這樣有可 03/02 15:05
6F：→ Morris1028: 可能比較快嗎？ 03/02 15:06
7F：→ FRAXIS: 你說的方法就類似 centroid decomposition 了 03/03 01:33
8F：→ DJWS: 路徑先從lca切兩段 兩段分開處理 針對一段路徑 每次找樹的 03/03 09:02
9F：→ DJWS: 重心 路徑長度只剩下不到一半 所以是log級別 03/03 09:02
10F：→ DJWS: ^^^^^^^^不是路徑長度 是剩下的節點數量 03/03 09:04
11F：推 DJWS: 等等 centroid decomposition如何計算一條路徑的權重? 03/03 09:17