Re: [问题] 树上路径和为 k
楼主: FRAXIS (喔喔) 2015-03-03 03:48:02
: 输入：一个 n 个顶点的树 T，每一个顶点 v 有一个整数权重 w(v)，及一整数 k。
: 输出：一条 T 上的路径（任意起点终点），其路径上顶点权重的总和为 k 。
: 推 DJWS: 能不能推荐几篇centroid/spine decomposition的教学资料? 03/02 08:14
http://wenku.baidu.com/view/60c6aa1ffc4ffe473368aba8.html
这个有介绍一下 centroid decomposition。
http://www.cnblogs.com/xiao_wu/archive/2010/06/01/1748728.html
一些相关问题
http://fanhq666.blog.163.com/blog/static/81943426201172472943638/
动态情况
我认真的搜寻了一下，我问的问题有出现在 zoj 2304 / poj 2114 Boatherds
http://blog.sina.com.cn/s/blog_5123df35010098vr.html
IOI 2011 也有这题
http://www.ioi2011.or.th/hsc/tasks/solutions/race.pdf
BZOJ 1758 是找出树上 length constrainted 的 maximum density path
https://www.byvoid.com/blog/wc2010-rebuild
网络上看的作法是O(n lg n lg RANGE)
理论上是可以做到O(n lg n) （spine decomposition）
可以参考 An optimal algorithm for the maximum-density path in a tree
: 输出：一条 T 上的路径（任意起点终点），其路径上顶点权重的总和为 k 。
: 推 DJWS: 能不能推荐几篇centroid/spine decomposition的教学资料? 03/02 08:14
http://wenku.baidu.com/view/60c6aa1ffc4ffe473368aba8.html
这个有介绍一下 centroid decomposition。
http://www.cnblogs.com/xiao_wu/archive/2010/06/01/1748728.html
一些相关问题
http://fanhq666.blog.163.com/blog/static/81943426201172472943638/
动态情况
我认真的搜寻了一下，我问的问题有出现在 zoj 2304 / poj 2114 Boatherds
http://blog.sina.com.cn/s/blog_5123df35010098vr.html
IOI 2011 也有这题
http://www.ioi2011.or.th/hsc/tasks/solutions/race.pdf
BZOJ 1758 是找出树上 length constrainted 的 maximum density path
https://www.byvoid.com/blog/wc2010-rebuild
网络上看的作法是O(n lg n lg RANGE)
理论上是可以做到O(n lg n) （spine decomposition）
可以参考 An optimal algorithm for the maximum-density path in a tree
作者: DJWS (...) 2015-03-03 09:01:00
谢谢! 所以没有spine decomposition的免费教学资料?
楼主: FRAXIS (喔喔) 2015-03-04 00:58:00
" target="_blank" rel="nofollow">