作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 树上路径和为 k
时间Mon Mar 2 00:24:46 2015
输入：一个 n 个顶点的树 T，每一个顶点 v 有一个整数权重 w(v)，及一整数 k。
输出：一条 T 上的路径（任意起点终点），其路径上顶点权重的总和为 k 。
这问题应该可以用O(n lg n)解出来，只是需要用centroid decomposition
或是 spine decomposition。
有没有比较好实作又有效率（o(n^2)）的解法？
另外我想问，有没有办法把这个问题转化成一个树，其权重是在边上而不是在
顶点上。因为大部分的文献都是考虑权重在边上的问题。
这是在 careercup 上看到的
http://www.careercup.com/question?id=2971
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.149
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1425227089.A.374.html
1F：推 fenzhang: 感觉枚举每个起点BFS就好 03/02 02:10
2F：→ FRAXIS: 但是要怎麽做成o(n^2)? 03/02 02:19
3F：推 DJWS: 能不能推荐几篇centroid/spine decomposition的教学资料? 03/02 08:14
4F：推 Morris1028: 考虑一条路径是否通过节点 v，每次找树的重心，假设存 03/02 15:05
5F：→ Morris1028: 有通过重心的路径为 k，反之没有则查找子树？这样有可 03/02 15:05
6F：→ Morris1028: 可能比较快吗？ 03/02 15:06
7F：→ FRAXIS: 你说的方法就类似 centroid decomposition 了 03/03 01:33
8F：→ DJWS: 路径先从lca切两段 两段分开处理 针对一段路径 每次找树的 03/03 09:02
9F：→ DJWS: 重心 路径长度只剩下不到一半 所以是log级别 03/03 09:02
10F：→ DJWS: ^^^^^^^^不是路径长度 是剩下的节点数量 03/03 09:04
11F：推 DJWS: 等等 centroid decomposition如何计算一条路径的权重? 03/03 09:17