CF1019E Raining season

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

题意：给出一棵树，每条边的边权是一个一次函数 .

当 时，分别求出树的直径。

，，时限 。

对于一条树上路径，设两种权值的和分别为 。

不难发现，若将其作为一个点，凸壳上的点才有可能成为答案。

下面的任务就是求出所有路径权值和组成的凸壳。

考虑边分治，求出两侧的向下路径组成的凸壳，然后跑闵可夫斯基和，即可合并。

实现中用 点分治 + 分治 代替了边分治，复杂度是一样的。

最后把得到的 个凸壳上的点再做一次凸包。

注意凸包中的重点和闵可夫斯基和中的零向量。

查询时在凸包上二分，本题可以将询问离线，依序单调扫一遍即可。

复杂度 。