Problem
Description
给定一棵 个点的树,点 有点权 ,树边带权。
定义 。
求 与 。
Constraints
Link
Solution
Analysis
对于任意一条路径 与任意点 ,容易知道 是 Convex function。
由 Convex function 的性质可知 与 均为 Convex function。
由这个性质可以发现:对于一个点 及所有与 相邻的点 ,至多只有一个 满足 。
因为若存在 及两个与其相邻的点 ,满足 ,则路径 不满足上述性质。
那么这个问题如果放在序列(路径)上,直接二分就可以了;相应地,树上的问题就可以用树上的二分也就是点分治来解决。
找满足 的 时,对 求导得到每个 相对于 的变化量,找到变化量小于 的那个 即可。
时间复杂度 。
Code
1 |
|