[問題] Distance In Tree

[singlovesong (~"~)]

you are given a tree with n vertices and a positive number k.
Find the number of distinct pairs of the vertices which have a distance of
exactly k between them. Note that pairs (v, u) and (u, v) are considered
to be the same pair.


        1<= n <= 50000
        1<= k <=500


沒想法＠＠

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.81.18.160
推 AmosYang: 用空間換時間的話，應該可在 O(n log n) 內解出來
→ AmosYang: 最慘也不過 O(n^2) ，暴力法硬上吧 :D
→ suhorng:codeforces...?
推 dreamoon:你可以參考http://codeforces.com/blog/entry/4097
→ dreamoon:Codeforces的比賽幾乎都會附參考解答
推 RockLee:是 161D 這題嗎? 網頁上說 solution 是 O(n k)?
→ RockLee:不是應該 O(n) 就能得到解了? 還是我理解有誤?
→ RockLee:感謝 D 大的說明, 我一開始的想法有少考慮的 scenario
→ RockLee:為了避免誤導, 我把我原本錯誤的解答刪掉了
→ singlovesong:看不懂-.-
推 DJWS:樓上不如說說看是哪裡看不懂
→ butterfly21:O(nk) by tree DP 也可以 O(n lg n) by 樹分治
→ butterfly21:前者實作上容易得多