PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 樹上路徑和為 k

看板Prob_Solve (計算數學 Problem Solving)作者 (喔喔)時間9年前 (2015/03/02 00:24), 編輯推噓4(4推 0噓 8→)
留言12則, 4人參與, 最新討論串1/3 (看更多)
輸入：一個 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://www.ptt.cc/bbs/Prob_Solve/M.1425227089.A.374.html
推
03/02 02:10, , 1F
感覺枚舉每個起點BFS就好
03/02 02:10, 1F
→
03/02 02:19, , 2F
但是要怎麼做成o(n^2)?
03/02 02:19, 2F
推
03/02 08:14, , 3F
能不能推薦幾篇centroid/spine decomposition的教學資料?
03/02 08:14, 3F
推
03/02 15:05, , 4F
考慮一條路徑是否通過節點 v，每次找樹的重心，假設存
03/02 15:05, 4F
→
03/02 15:05, , 5F
有通過重心的路徑為 k，反之沒有則查找子樹？這樣有可
03/02 15:05, 5F
→
03/02 15:06, , 6F
可能比較快嗎？
03/02 15:06, 6F
→
03/03 01:33, , 7F
你說的方法就類似 centroid decomposition 了
03/03 01:33, 7F
→
03/03 09:02, , 8F
路徑先從lca切兩段 兩段分開處理 針對一段路徑 每次找樹的
03/03 09:02, 8F
→
03/03 09:02, , 9F
重心 路徑長度只剩下不到一半 所以是log級別
03/03 09:02, 9F
→
03/03 09:04, , 10F
^^^^^^^^不是路徑長度 是剩下的節點數量
03/03 09:04, 10F
推
03/03 09:17, , 11F
等等 centroid decomposition如何計算一條路徑的權重?
03/03 09:17, 11F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1KyprHDq (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1KyprHDq (Prob_Solve)