题解：P9755 [CSP-S 2023] 种树

· · 题解

二分答案 m。

我们需要判断是否存在一个序列 \{d_n\} 表示对于每个 i，第 i 棵树如果在第 d_i 天种下，都要达到 a_i 的高度。

显然一棵树种的越早越好。我们可以求解一个 f(i) 表示第 i 棵树最晚在第几天种可以满足要求。

假设我们已经求好了。不难发现一个必要条件是：

对于所有 1 \le i \le n，满足 f(u) \le i 的数量必须 \le i。

但不充分。

显然对于一条树边 (fa_u, u) 而言，有 d_{fa_u} \le d_u - 1。这是因为你从 1 扩展到 u 必须经过 fa_u。那么我们可以 \operatorname{chkmin}(f_{fa_u}, f_u-1)，以得到实际的 f。

此时上面的条件充分。

简洁证明：

首先这样做完后 f 一定是一个小根堆的形态。即祖宗的权值一定 \le 儿子的权值。

那么所有满足 f(u) \le i 的 u 在树上一定是一个包含根的连通块。令这样的 u 的数量为 c。显然我们可以用 c 天时间将这些点上种上树。因为 c \le i 所以这些点都可以满足要求。

对于所有的 i，上面的分析均成立。所以这样做是正确的。

考虑求解更新前的 f(i)，即第 i 棵树最晚在第几天种可以满足要求。

令 s(i, l, r) 表示第 i 棵树在第 l \sim r 天内增长的高度。那么原问题等价于是否对于所有 i 都满足：

s(i, d_i, m) \ge a_i

显然可以差分。令 g(i, j) = s(i, 1, j)，则 s(i, l, r) = g(i, r) - g(i, l - 1)。即：

g(i, m) - g(i, d_i) \ge a_i

注意到 d_i 越小越好。所以我们二分 d_i。所以现在的任务是求解 g(i, m)。由定义知：

g(i, m) = \sum_{j=1}^m \max(b_i + j \times c_i, 1)

分类讨论：