【洛谷P4149】Race

題目

題目連結：https://www.luogu.com.cn/problem/P4149

給一棵樹，每條邊有權。求一條簡單路徑，權值和等于 \(k\)，且邊的數量最小。

思路

考慮點分治。假設目前根節點為 \(rt\)，便利 \(rt\) 的每一個子樹，設 \(mind[x]\) 表示其中一個端點為 \(rt\)，長度為 \(x\) 的路徑最短深度，枚舉每一棵子樹的時候，将路徑長度不超過 \(k\) 的路徑的最短深度記錄到 \(maxd2\) 中，然後枚舉該子樹内每條路徑長度，與 \(mind\) 進行比對。

注意每次 calc 之後需要清空。不能使用 memset。

時間複雜度 \(O(n\log n)\)。

代碼