标签为 [点分治] 的文章

BZOJ2599 Race(点分治)

题目大意 给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小。 Solution 如果我们能知道这棵树里的任意一棵子树,我们一定可以用${size}log_{size}$的复杂度(size表示子树大小)计算出这棵子树内通过根的所以符合条件的路径。具体实现枚举这个根的每棵子树,用map维护一下就好了。(map大法好)。 用分治的思想,计算完整棵树后,把它分成若干棵相同结构的子树,再计算答案。所以只要能找到一个合适的分治点,就可以得到较好的复杂度。 具体实现时,可以找到整棵树的重心,把它作为根,并将它作为分治点继续分治。 因为 ......