zhangxyhp

摘要： 問題顯然可以分為兩部分：\(u\) 的子樹內和 \(fa_u\) 到 \(v\) 的鏈上。前者需要樹上背包，后者需要取 \(\max\)。 考慮用線段樹維護這兩個值。子樹內的答案只需要一次區間查詢，再加上樹上背包的 \(O(m^2)\)，總共為 \(O(m^2\log n)\)。鏈上的答案需要進行樹 閱讀全文