[BZOJ2599/Luogu4149][IOI2011]Race(点分治)

发布于 2018-02-26  142 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2599/Luogu4149][IOI2011]Race(点分治)

Description

给一棵树,每条边有权。求一条简单路径,权值和等于 K ,且边的数量最小。

Http

BZOJ
Luogu

Tag

点分治

解决思路

考虑点分治。对于一个重心,我们需要求出一条过重心的合法路径,那么可以考虑开桶,记\(Min[i]\)表示与重心距离\(i\)的经过的边最短的点的编号。那么,接下来的问题是如何不重不漏地找到解。
考虑到我们已经要求这条路径一定要经过当前重心,那么一条合法的路径要么就是直接从重心出发,要么是由两条不同子树的两条路径组合而成的。那么可以考虑计算当前子树答案的时候,先不用它取更新\(Min\)数组,这样可以保证当前答案一定从前面其他子树更新过来,遍历完这一子树后,再把这棵子树的去更新\(Min\)。
需要注意的是,为了保证时间效率高效,每一次初始化\(Min\)不要用\(memset\)。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2599/Luogu4149][IOI2011]Race(点分治)


HNCJ OIer