本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-13 15:18:30

不算难。难点在于 CCF 独有的鹅心大分桃。

答案的单调性是显然的：第 $x$ 天能完成，$x + 1$ 天也定能完成，于是二分一个 $m$ 作为答案，并转化为判定问题。

每棵树每天的增量是不小于一的，但是正由于这个一的下界，我们需要一个有点恶心的分桃。

忽略角标，我们设 $g(x)$ 表示从 $1$ 开始种，种到 $x$ 时刻的总高度，设 $z = \max \{0, \lceil\dfrac{1-b}c\rceil\}$ 是使得增量为一的点，定义域非负。

当 $x \lt z$ 时显然有 $g(x)= bx + \dfrac 1 2 cx(x + 1)$；

当 $x \ge z$ 时：

• $c\gt 0$，$g(x) = z + b(x - z) + \dfrac 1 2cx(x+1)-\dfrac 1 2 cz(z + 1)$

• $c = 0$，$g(x) = bx$

• $c \lt 0$，$g(x) = bz + \dfrac 1 2 cz(z + 1)+(x-z+1)$

很难说这种傻逼线性柿子有什么意义，但凡换成随便其它一个不需要分桃的单调函数都行。但是出了就得做。。

$g(x)$ 单调性显然，我们需要二分找到最大的 $t$ 使得 $g(t) \ge a$ 且 $g(t+1)\lt a$，即种这棵树的最晚入口。$t\le m$ 是显然的，不满足直接跳出。

找到所有的 $t$ 后，问题就转化为了：对每个点，我们为其分配一个 $x$ 使得 $1\le x \le t$ 且 $x_{\text{fa}_i}\lt x_i$，且 $x$ 不重。

那么我们按照 $t$ 排序，优先满足 $t$ 小的即可。

复杂度是两支 $\log$ 的，对应两个二分。