作者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