CF1019E Raining season

一辈子也不写闵可夫斯基和了。

题目链接： CF1019E Raining season 。

题目描述：

给一棵树，边权是一次函数 $a_ix+b_i$ 的形式。求当 $x=0,1,\cdots,m-1$ 时的树的直径。

$n\le10^5,m\le10^6$ 。

首先对于某一个路径的一次函数 $kx+b$ ，为了求在 $x=0,1,\cdots,m-1$ 时的最值，我们应该把他表示为平面直角坐标系的 $(k,b)$ ，那么最后的答案就是所有路径的点对的凸包。

然后对于路径，我们应该点分治。那么对于一次的分治中心 $x$ ，我们应该求出他的分治子树的所有点到 $x$ 的路径的点对所形成的凸包。最后在把每个分治中心得到的凸包暴力合并就行了。问题在于如何合并两条从 $x$ 出发路径。容易发现原来的 $(k_1,b_1)$ 和 $(k_2,b_2)$ 应该合并为 $(k_1+k_2,b_1+b_2)$ ，这是一个闵可夫斯基和的形式。所以我们只需要求出每个分治子树的凸包，最后合并答案就行。但是这样还是有问题。因为我们只能合并两条路径，但是闵可夫斯基和做不到这样。所以我们应该采取类似于左偏树初始化的手法，每次取出前两个凸包，然后闵可夫斯基和求答案，然后把这两个凸包对应位置取 $\max$ 。然后把他们扔到末尾。

然而，上述方法过于麻烦，预期要写 $8KB+$ 。上述做法瓶颈在于使用类似于左偏树初始化的手法合并而不是直接用闵可夫斯基和合并。为了能让闵可夫斯基和直接合并，每一个分治分治中心必须有两个儿子。然后一段关于去年你刚学点分治的记忆出现，……，我们应该使用边分治代替点分治！这样就可以直接使用闵可夫斯基和合并了。

最后求答案是凸包二分就行。

代码比较好些，因为每个模块是固定无交集的。我写了 $6KB$ ，代码不放了。