作者singlovesong (~"~)
看板Prob_Solve
標題[問題] Distance In Tree
時間Mon Mar 12 01:24:18 2012
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
1F：推 AmosYang: 用空間換時間的話，應該可在 O(n log n) 內解出來 03/12 01:49
2F：→ AmosYang: 最慘也不過 O(n^2) ，暴力法硬上吧 :D 03/12 01:50
3F：→ suhorng:codeforces...? 03/12 08:25
5F：→ dreamoon:Codeforces的比賽幾乎都會附參考解答 03/12 08:50
6F：推 RockLee:是 161D 這題嗎? 網頁上說 solution 是 O(n k)? 03/12 09:16
7F：→ RockLee:不是應該 O(n) 就能得到解了? 還是我理解有誤? 03/12 09:16
8F：→ RockLee:感謝 D 大的說明, 我一開始的想法有少考慮的 scenario 03/12 09:43
9F：→ RockLee:為了避免誤導, 我把我原本錯誤的解答刪掉了 03/12 09:43
10F：→ singlovesong:看不懂-.- 03/12 15:14
11F：推 DJWS:樓上不如說說看是哪裡看不懂 03/12 19:28
12F：→ butterfly21:O(nk) by tree DP 也可以 O(n lg n) by 樹分治 03/13 11:14
13F：→ butterfly21:前者實作上容易得多 03/13 11:14