凸函数的 卷积等价于差分数组的归并。

容易想到 DP：设 表示在 子树内有 个黑点， 子树内的边代价和最小值。

那么转移如下： 容易发现 是凸的，那么第一条转移中的凸函数 卷积就是差分数组的归并。因为此时 卷积的组合意义就是选择第一个差分数组中前 小之和与第二个差分数组前 小之和贡献到位置 ，那么贪心地选归并后的前 小肯定是最优的。

第二条相当于在差分数组里插入一个 。

第三条则是差分数组一段前缀减、一段后缀加。

使用 splay 启发式合并差分数组即可做到 。

但可以更简单，观察到每次加的一次函数的分段点都是固定的，所以可以考虑维护对顶堆，保证左边堆的大小恒为 。那么三操作就是对两个堆打加法标记，用左偏树等可并堆维护即可。也可做到 。