推 fenzhang: 感覺枚舉每個起點BFS就好 03/02 02:10
→ FRAXIS: 但是要怎麼做成o(n^2)? 03/02 02:19
推 DJWS: 能不能推薦幾篇centroid/spine decomposition的教學資料? 03/02 08:14
推 Morris1028: 考慮一條路徑是否通過節點 v，每次找樹的重心，假設存 03/02 15:05
→ Morris1028: 有通過重心的路徑為 k，反之沒有則查找子樹？這樣有可 03/02 15:05
→ Morris1028: 可能比較快嗎？ 03/02 15:06
→ FRAXIS: 你說的方法就類似 centroid decomposition 了 03/03 01:33
→ DJWS: 路徑先從lca切兩段 兩段分開處理 針對一段路徑 每次找樹的 03/03 09:02
→ DJWS: 重心 路徑長度只剩下不到一半 所以是log級別 03/03 09:02
→ DJWS: ^^^^^^^^不是路徑長度 是剩下的節點數量 03/03 09:04
推 DJWS: 等等 centroid decomposition如何計算一條路徑的權重? 03/03 09:17