Re: [问题] 树上路径和为 k

楼主: FRAXIS (喔喔)   2015-03-05 03:08:43
※ 引述《FRAXIS (喔喔)》之铭言:
: : 推 DJWS: 能不能推荐几篇centroid/spine decomposition的教学资料? 03/02 08:14
就我有限的理解,我说明一下 spine decomposition ,大家可以讨论。
首先考虑一个简单的问题
输入: 一条 n 个点的路径,边上有权重及长度(可正可负),以及一数字 U 。
输出: 长度和小于 U 子路径中,最大的权重和。
这问题跟 maximum sum subarray 很类似,只是差在长度不是 uniform 。
考虑两种 divide and conquer 算法。
1. 类似 quick sort
找出路径的中点 m ,计算出通过 m 满足条件的最大权重子路径。
这步会花 O(n lg n)的时间。
然后借由 m 把路径分成两半,分别计算出只在该部份的最大权重子路径。
总时间会是 O(n lg^2 n)。
2. 类似 merge sort
找出路境的中点 m 。
计算第一个点到 m 的最大权重子路径,
以及把结尾在 m 的所有路径按照长度排序。
计算第 m + 1 个点到 n 的最大权重子路径,
以及把结尾在 m + 1 的所有路径按照长度排序。
借由两半部的路径,找出通过 m 且满足条件的 最大权重子路径。
这步会花 O(n) 时间,总时间是 O(n lg n)。
很明显方法 1 在 计算通过 m 满足条件的最大权重子路径时有些重复计算。
所以方法 2 效率比较好。
然后把输入从路径改成树,思考最大权重子路径问题。
如果用 centroid decomposition,每次要计算出通过 centroid 且满足
条件的路径,需要花 O(n lg n),这导致最后时间复杂度变成O(n lg^2 n)。
不过其实其中有一些是重复的计算。
这边我想不太到有没有什么方法可以利用子树的计算来辅助,
主要是一个树可能会被从不同地方切开,一个子树可能会跟一堆其他树相接,
很难维护计算结果。
spine decomposition 不是用一个点把树切开,而是用一条 path 把
树切开,切开之后不是两半,而是一堆子树,每个子树与 path 的一个点
相接。
递回算出每个子树中最大权重子路径,
同时算出在每个子树中,终点在 path 上的所有路径按照且长度排序。
然后我们就可以在 path 上用类似方法 2 来 merge 了,
当然这边 merge 需要有技巧,要保证 merge 的两个子树差不多大,
而且 merge 两个子树只能花 O(n) 的时间。
不知道有长度下界的时候,能不能也做到O(n lg n)。
楼主: FRAXIS (喔喔)   2015-03-07 22:10:00
我发现这好像只是Heavy path decomposition的应用..

Links booklink

Contact Us: admin [ a t ] ucptt.com