CF566C Logistical Questions

发表于 分类于 ， ， 阅读次数：

题意：给出一棵 个点的无根树，点有点权 ，边有边权，均非负。

求一个点 使得 最小。

，时限 。

首先观察性质：给定 后， 是凸函数，凸函数的和仍然是凸函数。

对于任意一条路径上的 ，代价 都是凸的。

这就告诉我们，整颗树的代价必然朝着一个中心（也就是我们要找的最小值点）单调下降。

我们可以先选取一个点，求出代价，然后比较相邻点的代价，往唯一的代价小的点走。

考虑点分治，每次向更低的联通块找重心，这样可以保证移动不超过 次。

问题在于中心的度数可能很大，对每个相邻点都计算代价会很慢。

如何判断函数的增减趋势？不难想到求导。

先求出每个子树的导数和，由线性性易求。

具体咋求：，这里 是深度，是点权，由于只用于比较，可以把常系数省略。

然后查看其他子树的导数和减去某个子树的导数和，如果为负数则表明这里低。

不过，我们在这里强行把离散函数变成了连续函数，最后一跳可能取在某条边的中间，这时需要把两个端点都试一试。

复杂度 。