[点分治记录] P4292 [WC2010]重建计划

题目

看到需要求的柿子首先想到分数规划。也就是二分答案，然后在check里将所有边权减去$mid$，检验是否有路经权值$\ge$0。

现在问题转化成求路径长度在 $[l,r]$ 范围内的权值和最大的路径。

考虑使用点分治解决这道题，而上面的问题与点分治模板题只差两点：

1. 要求路径权值和最大而非一个固定值。

2. 长度在 $[l,r]$ 范围内而非一个固定值。

上面两点的处理方式：

（1）用桶记录深度为 $dep$ 的点，到目前选的重心的最大距离。（注意这里 $dep$ 不是原树的 $dep$，实际上是原树该点的 $dep$ 减去目前的重心的 $dep$）

（2）在使用该点的已处理子树的信息与该点目前正在处理的子树的信息修改答案时，肯定不能同时枚举在已处理的子树中选择的点的$dep$值和目前正在处理的子树中选择的点的$dep$值，所以考虑优化这一部分。假设在已处理的子树中选择的点的 $dep$ 为 $dep_1$，在目前正在处理的子树中选择的点的 $dep$ 为 $dep_2$，可以保留枚举 $dep_2$ 的这一层循环，即第一层循环正常枚举 $dep_2$。由于 $dep_1+dep_2$ 的值在 $[l,r]$ 范围内，所以$dep_1$ 的范围是 $[l-dep_2,r-dep_2]$，即可使用单调队列进行维护。

所以这道题就做完了。