ARTICLE · 1121625

真题解析:P9755 [CSP-S 2023] 种树(二分答案·等差数列求和·树上逆向贪心·优先队列)

发布时间：2026-10-04 09:50:11 最近访问：2026-10-04 09:50:11

题目来源：洛谷 P9755 [CSP-S 2023] 种树

题目大意

森林地图上有 n 片地块，1 号地块连接森林入口，n−1 条道路把所有地块连成一棵树。起初每片地块都没有树。

你每天可以选一个未种树、且与某个已种树地块直接相邻的地块，种下一棵高度为 0 米的树；第 1 天只能在 1 号地块种。如果所有地块都已经种过树，当天就不操作。

地块 i 上的树，在全局第 x 天会长高 max(b_i + x × c_i, 1) 米。注意 x 是从任务第一天开始算的全局天数，不是这棵树种下后的第几天。也就是说，一天里所有已经种下的树都在同时长高，越早种下的树累计的生长天数越多。

要求每片地块 i 上的树高度都不低于 a_i 米，求最少需要多少天。

数据范围：n 最大 10 的 5 次方，a_i 最大 10 的 18 次方，b_i 最大 10 的 9 次方，c_i 的绝对值最大 10 的 9 次方，时间限制 1 秒。题目保证 10 的 9 次方天内一定有可行方案。

输入输出样例

样例输入 #1

412 1 12 4 -110 3 07 10 -21 21 33 4

样例输出 #1

一种最优安排是：第 1 天种 1 号，第 2 天种 3 号，第 3 天种 4 号，第 4 天种 2 号。到第 5 天结束时，四片地块的树高分别是 20、2、12、7 米，都达到了要求。而 4 天是不够的——4 天内必须把 4 棵树全部种完，此时 3 号地块最早只能在第 2 天种下，到第 4 天累计只有 9 米，达不到 10 米，所以答案是 5。

样例 2、3、4 的数据量较大，见题目附件的 tree/tree2.in、tree/tree3.in、tree/tree4.in。

考点梳理

考点	在本题里的作用
二分答案	天数越多越容易达标，可行性随天数单调，对最少天数二分
等差数列求和	一段连续天数内的累计生长量可以常数时间算出，不必逐天模拟
分段函数 max(... , 1)	c_i 小于 0 时生长量会掉到 1 米，需要找分界点分成两段处理
树上约束转化	「父节点比子节点先种」可以转化成每个点的最晚种植日约束
逆向贪心 + 优先队列	从第 n 天倒着排种植日，每天挑最晚种植日最大的点排在这一天
128 位整数	高度求和会突破 64 位整数上限，需要 `__int128`

解题思路

一、为什么可以二分答案

关键观察在生长公式里：单日生长量是 max(b_i + x × c_i, 1)，外面这个 max(..., 1) 意味着不管公式算出多小的值，当天至少长 1 米。

于是每个点已经种下之后，累计高度只增不减；把总天数从 D 加大到 D+1，任何点的累计生长量只会变多，不会变少。也就是说「D 天够不够」这个判定是单调的：D 够则 D+1 一定也够。既然单调，就可以二分最小的可行 D。

二分区间取 [n, 1e9]：下界是 n，因为 n 片地块至少每天种一棵、要 n 天；上界是题目保证的 1e9 天。

对应代码里 main 的这两句：

const ll MAXDAY = 1e9;ll l = n, r = MAXDAY;

二、grow：一段天数里的累计生长量

要判定 D 天够不够，第一步得知道「某个点在某段时间里一共长了多少」。这里定义函数 grow(i, l, r)，表示点 i 从第 l 天种下、一直长到第 r 天，累计长了多少米：

grow(i, l, r) = Σ (x 从 l 到 r) max(b[i] + x × c[i], 1)

先把 max(..., 1) 放一边，单看 b + x × c 的和。天数长度记作 len = r - l + 1，那么：

• 常数项 b 一共加了 len 次，贡献 b × len
• 一次项是 c 乘以 l + (l+1) + ... + r，这段等差数列的和是 (l + r) × len / 2

合起来就是累加公式 b × len + c × (l + r) × len / 2，常数时间算完。

麻烦在于 max(..., 1) 让这个函数分了段。当 c_i 不小于 0 时，b + x × c 随 x 单调不减，而且 b_i 至少是 1，所以整段都取公式值；当 c_i 小于 0 时，生长量先大后小，会在某一天掉到 1 米以下，从那天起每天都只能按 1 米算。

分界点就是满足 b + x × c 不小于 1 的最大 x，即 x = (1 - b) / c。因为 c 是负的，除法结果自然向下取整，正好是我们要的位置。于是代码分成三种情况：

• 情况 1：c 不小于 0，或者右端点 b + r × c 仍然大于 0 —— 整段都用公式；
• 情况 2：左端点 b + l × c 已经不高于 0 —— 整段都只能取 1，直接返回长度；
• 情况 3：左端大于 0、右端不高于 0 —— 前一段 [l, x] 用公式，后一段 [x+1, r] 每天算 1 米。

对应代码：

ll len = r - l + 1;

求和的时候必须用 128 位整数：len 可以到 10 的 9 次方，c 也可以到 10 的 9 次方，乘起来到了 10 的 27 次方的量级，早就超出了 64 位整数的范围。所以代码里 ll 是 long long，lll 是 __int128，只要涉及乘法就用 lll 把参与运算的数先撑开。

三、latest：二分求每个点的最晚种植日

有了 grow，就可以回答「某个点最晚能拖到第几天种」。

固定总天数 day 之后，一个点种得越晚，它能长高的天数就越少，累计高度也越低。所以「能不能在第 t 天种下」这个判断对 t 也是单调的：t 可行则更早一定可行，t 不可行则更晚一定也不行。于是可以二分最大的可行 t。

二分时用 mid = (l + r + 1) >> 1 这种偏右的中点，因为要找的是「最大的可行值」，用偏右中点才能保证区间一定收缩、不会死循环。二分区间是 [1, day]，初始的中点是第 1 天。如果连第 1 天种下都长不到 a[i]，就直接返回 −1，宣告这个 day 不可行。

返回的这个最晚种植日，就是代码里的 ddl[i]：

ll latest(int i, ll day){    if (grow(i, 1, day) < a[i]) return -1;    ll l = 1, r = day;    while (l < r) {        ll mid = (l + r + 1) >> 1;        if (grow(i, mid, day) >= a[i]) l = mid;        else r = mid - 1;    }    return l;}

四、check：树上逆向贪心排期

算出所有点的 ddl[i] 之后，问题变成：能不能把这 n 个点安排到第 1 天到第 n 天（一天种一棵，一共 n 棵）？

这里有两条约束：

1. 父节点必须比子节点先种。因为每天只能种与已种地块相邻的地块，从 1 号地块出发往外扩散，实际效果就是父节点一定排在子节点前面。
2. 每个点 i 的种植日不能超过 ddl[i]，否则它长不到 a_i。

做法是从第 n 天倒着往第 1 天填。倒着看有一个好处：能排在后面的点，一定是它的子树已经全部排完了（最先是叶子，最后轮到根）。

维护一个 rem[i] 数组记录「i 还有几个儿子没排期」。一开始只有叶子满足 rem 为 0，它们先入堆；堆里存 {ddl[i], i}，是大根堆，每次取 ddl 最大的那个点，安排在当天。为什么挑 ddl 最大的？因为这批点都是「当天就能排」的，把最不急的（最晚种植日最大的）往后放，把早的日子留给更急的点，这就是贪心的道理。

某个点 u 排完之后，它父亲 fa[u] 就少了一个待排的儿子：--rem[fa[u]]。当父亲的 rem 减到 0，说明它的所有儿子都排在更晚的日子了，父亲这时才能入堆。

两种情况下判定失败：

• 某点被排到第 t 天，但 ddl[u] 比 t 还小，说明它最晚也只能在更早的日子种下，来不及了；
• 堆已经空了，却还有日子没填，说明树的依赖关系填不满这些天。

对应代码：

priority_queue<pair<ll, int>> pq;for (int t = n; t >= 1; t--) {    if (pq.empty()) return false;    int u = pq.top().second;    pq.pop();    if (ddl[u] < t) return false;    int p = fa[u];    if (p && --rem[p] == 0) pq.push({ddl[p], p});}

五、主函数：建树与二分答案

主函数先把数据读进来，然后以 1 号地块为根建树。建树时用栈来模拟 DFS，因为 n 到 10 的 5 次方，递归写法可能爆栈。遍历过程中记下每个点的父亲 fa[u]，以及儿子个数 son[u] —— 后者在 check 里初始化 rem 要用。

最后在 [n, 1e9] 上二分答案。这里的判定用左闭右开式的写法：check(mid) 成立就把右界收到 mid，否则把左界抬到 mid+1。二分结束时左右界重合，就是最少天数。

ll l = n, r = MAXDAY;while (l < r) {    ll mid = (l + r) >> 1;    if (check(mid)) r = mid;    else l = mid + 1;}cout << l << '\n';

六、易错点

漏掉 max(·,1)。生长公式是 max(b + x × c, 1) 而不是 b + x × c。c 小于 0 时，后期公式值会变成 0 甚至负数，如果漏掉这个下限，累计高度会算少，答案偏大。

x 的含义搞错。x 是全局第几天（从 1 开始），不是「种下后的第几天」。同一棵树种在第 3 天和第 5 天，同一天长的高度是一样的，区别只在于累计了多少天。

求和溢出。天数可以到 10 的 9 次方，c 也可以到 10 的 9 次方，乘起来到 10 的 27 次方量级，必须用 __int128。整份代码里 grow 的返回值、以及求和过程中的中间量都要注意这一点。

分界点取整方向。c 小于 0 时，(1 - b) / c 依靠 C++ 向零取整得到向下取整的结果，这是对的；但如果换个写法或者换个语言，取整方向可能反过来，分界点就会错开一天。

二分找最大可行值要用偏右中点。latest 里如果写成 (l + r) >> 1，当 l 和 r 只差 1 且 l 可行时，区间不会收缩，循环出不来。

参考代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef __int128 lll;const int MAXN = 1e5 + 10;const ll MAXDAY = 1e9;int n;ll a[MAXN], b[MAXN], c[MAXN];ll ddl[MAXN];int fa[MAXN], son[MAXN], rem[MAXN];vector<int> adj[MAXN];lll grow(int i, ll l, ll r){    if (l > r) return 0;    ll len = r - l + 1;    if (c[i] >= 0 || b[i] + (lll)r * c[i] > 0) {        return (lll)b[i] * len + (lll)c[i] * (l + r) * len / 2;    }    if (b[i] + (lll)l * c[i] <= 0) {        return (lll)len;    }    ll x = (1 - b[i]) / c[i];    return (lll)b[i] * (x - l + 1)    + (lll)c[i] * (l + x) * (x - l + 1) / 2    + (r - x);}ll latest(int i, ll day){    if (grow(i, 1, day) < a[i]) return -1;    ll l = 1, r = day;    while (l < r) {        ll mid = (l + r + 1) >> 1;        if (grow(i, mid, day) >= a[i]) l = mid;        else r = mid - 1;    }    return l;}bool check(ll day){    for (int i = 1; i <= n; i++) {        ddl[i] = latest(i, day);        if (ddl[i] < 1) return false;        rem[i] = son[i];    }    priority_queue<pair<ll, int>> pq;    for (int i = 1; i <= n; i++) {        if (son[i] == 0) pq.push({ddl[i], i});    }    for (int t = n; t >= 1; t--) {        if (pq.empty()) return false;        int u = pq.top().second;        pq.pop();        if (ddl[u] < t) return false;        int p = fa[u];        if (p && --rem[p] == 0) pq.push({ddl[p], p});    }    return true;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    cin >> n;    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];    for (int i = 1; i < n; i++) {        int u, v;        cin >> u >> v;        adj[u].push_back(v);        adj[v].push_back(u);    }    fa[1] = 0;    vector<int> st = {1};    while (!st.empty()) {        int u = st.back();        st.pop_back();        int cnt = 0;        for (int v : adj[u]) {            if (v == fa[u]) continue;            fa[v] = u;            cnt++;            st.push_back(v);        }        son[u] = cnt;    }    ll l = n, r = MAXDAY;    while (l < r) {        ll mid = (l + r) >> 1;        if (check(mid)) r = mid;        else l = mid + 1;    }    cout << l << '\n';    return 0;}

复杂度分析

设答案上界为 D，本题 D 不超过 10 的 9 次方，所以外层二分大约 30 次。

grow 是常数时间；latest 内部还要再二分一次，是 O(log D)；check 里对 n 个点各调一次 latest，再用优先队列排 n 个点，单次 check 是 O(n log D + n log n)。

外面套上二分答案的 O(log D) 层，总复杂度是 O(n log² D + n log n log D)。取 n = 10 的 5 次方、log D 约 30，大约是 10 的 8 次方级别，在 1 秒的时限内可以跑过。