输入：一个 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

感觉枚举每个起点BFS就好

但是要怎么做成o(n^2)?

能不能推荐几篇centroid/spine decomposition的教学资料?

考虑一条路径是否通过节点 v，每次找树的重心，假设存有通过重心的路径为 k，反之没有则查找子树？这样有可可能比较快吗？

你说的方法就类似 centroid decomposition 了

路径先从lca切两段 两段分开处理 针对一段路径 每次找树的重心 路径长度只剩下不到一半 所以是log级别^^^^^^^^不是路径长度 是剩下的节点数量等等 centroid decomposition如何计算一条路径的权重?http://www.ugrad.cs.ubc.ca/~cs490/2014W2/pdf/jason.pdf