秘仪「后户的狂言」/ 另解 CF932F

fjy666 · 2023-05-16 18:55:27 · 题解

可以列出一个显然的 dp 方程 f_u = f_v+ a_ub_v(v\in\rm{Subtree_u})，f_u 代表结点 u 的答案。

大部分题解选择用 李超树合并 来处理上面的信息，但是在这里我将给出一个较为简单的方法。

我们先处理处每个结点的 dfn 序，那么可以拿来更新 f_u 的 v 属于 (\mathrm{dfn}_u,\mathrm{dfn}_u+\mathrm{siz}_u) 。
把这个放到线段树上，相当于要处理一下两个操作

• 往位置 p 插入一条直线 l。
• 查询 [l,r] 中所有直线在 x=q 时的 \min\{y\}。

很容易发现 可能 产生答案的直线形成一个凸壳，且斜率单调递减。

如果每次插入直线都要重构整个凸壳复杂度无法承受。
此时有两种选择：

• 平衡树维护凸壳（CF70D plus）
• 只在一个结点中所有线段都被插入后再重构（SDOI2014 向量集）

显然，每当你询问一个区间 [l,r]，那么所有编号在 [l,r] 之间的直线都在线段树内了，所以第二种方法是正确的。

重构总次数为线段树节点个数 =\mathcal{O}(n\log n)。
总时间复杂度 \mathcal{O}(n\log^2n)。

参考代码实现。