今天看 CSP-S 2023 的这道题，考点是二分答案。
题目来源：ACGO A7095 ｜ 洛谷 P9755
难度定位：提高+/省选- ｜ 通过率：50.00%
一、题目信息
题目名称：种树
所属赛事：2023 年 CSP-S 组复赛
官方难度：提高+/省选-
涉及知识点：二分答案
题目链接：https://www.acgo.cn/problemset/info/7095
洛谷编号：P9755（同一道题，两个平台均可提交，代码通用）
易错点（很多人栽在这）
- 左右边界的更新要成对写，边界写错容易死循环
- 判断函数必须是单调的，否则二分不成立
- 高难度题的暴力分很关键，先写一版能过的部分分再想正解
题意简述
题意其实很直白：
你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。
森林的地图有 n 片地块，其中 1 号地块连接森林的入口。共有 n-1 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。
你的目标是：在每片地块上均种植一棵树木，并使得 i 号地块上的树的高度生长到不低于 a_i 米。
你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相连）的地块，种一棵高度为 0 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 1 天你只能在 1 号空地种树。
对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 x 天，i 号地块上的树会长高 max(b_i + x × c_i, 1) 米。注意这里的 x 是从整个任务的第一天，而非种下这棵树的第一天开始计算。
你想知道：最少需要多少天能够完成你的任务？
前置知识
这题要用到的工具不多，但有一个容易忘，先过一遍。
在有序区间里折半
二分本身简单，难在判断「答案是否单调」。只要满足「x 可行则 x+1 也可行」，就能二分答案。
二、思路分析
这题官方难度提高+/省选-，中场，先拿暴力分比较稳妥。
思路的入口在哪里？
题意解析
我们首先来考虑链的部分分。
不难发现，这部分的关键是实现一个形如check(x,l,r)的函数，表示 x 结点在 [l,r] 这段时间的生长高度能否达成目标。同时，这也是正解的一个关键函数。
不妨列出 x 结点高度的表达式：
先考虑c_x>=0的情况，则可以化简
接着我们思考特殊性质。
不难发现此时每个结点生长到目标高度所需时间与种下的时间无关，即有{t_x}=a_x/b_x向上取整。
将结点{t_x}按从大到小排序。考虑这样一个贪心，我们顺次考虑所有结点，若该结点已被种树就跳过，否则将根到该结点这条链按顺序把未种树的结点种树。显然这样做会得到一个种树顺序的序列，显然由于{t_x} 更小的结点不是时间的瓶颈，我们这样做是最优的。
实际实现过程中，我们标记一下每个结点是否种过树。当考虑当前结点 x 时，暴力跳到最后一个未被标记的祖先结点，然后倒序再给每个结点赋上开始种树的时间s_x。取 s_x+t_x-1 的最大值即可。
想明白了前两个部分，正解就是容易的。
考虑一般情况与特殊性质的区别，不难发现我们无法得到上述的 t_x了，究其根本是因为树种下的时间会影响种树需要的时间。
我们考虑二分答案，并修改t_x 的定义为要使该结点合法的最晚种树时间。显然在该前提下，t_x 可以用二分答案加上链部分所实现的函数求出。而这时我们按照t_x 从小到大考虑，不难发现问题就转化为了特殊性 时的问题，套用以上做法即可解决。
时间复杂度O(nlognlogv)。用桶排并上二次函数相关知识应该能将logn 去掉，不过没必要。
三、完整代码
#include <cstdio> #include <algorithm> #include <vector> using namespace std; // CSP-S 2023 种树 // // 题意：n 个地块构成一棵以 1 为根的树。每天可以选一个「未种树、且与已种树的 // 地块相邻」的地块种一棵高度为 0 的树。第 x 天，i 号地块的树长高 // max(b_i + x*c_i, 1) 米（x 从整个任务第 1 天算起，不是种下的那天）。 // 要求最终每片地块的树高 ≥ a_i，求最少天数。 // // 思路：二分答案 D，判定 D 天是否可行。 // // 1. 对每个地块 i，求出「最晚可以第几天种下」lim[i]： // 若第 t 天种下，则到第 D 天累计长高 G(i,t) = Σ_{x=t..D} max(b_i + x*c_i, 1)。 // G(i,t) 随 t 增大单调不增，因此 lim[i] 就是满足 G(i,t) ≥ a_i 的最大 t。 // 求 lim[i] 用二分（对 t 二分，G 用等差数列公式 O(1) 计算）。 // （因为 max(...,1) 的存在，把 [t,D] 分成两段：b_i + x*c_i < 1 的部分按 1 累加， // 其余按 b_i + x*c_i 累加，用等差数列求和即可。） // 2. 树上「父必须先于子」：把 lim 自底向上收紧 lim[fa] = min(lim[fa], lim[child] - 1)。 // 3. 若所有 lim[i] ≥ 1，把 n 个地块按 lim 升序排列，第 k 个必须安排在第 ≤ lim 的天； // 只需检查第 k 个的 lim ≥ k（k 从 1 开始）。全部满足则 D 可行。 // // 复杂度：二分 O(log(1e9)) × 判定 O(n log D)，n ≤ 1e5 时总计约 O(n log²)，可过。 const int MAXN = 100005; const long long INF = (long long)4e18; int n; long long a[MAXN], b[MAXN], c[MAXN]; int head_[MAXN], nxt_[2 * MAXN], to_[2 * MAXN], ecnt; int par[MAXN], ord_[MAXN], ordn; inline void addEdge(int u, int v) { to_[++ecnt] = v; nxt_[ecnt] = head_[u]; head_[u] = ecnt; } void buildTree() { static int stk[MAXN], state[MAXN]; for (int i = 1; i <= n; ++i) { par[i] = 0; state[i] = 0; } int sp = 0; par[1] = 0; stk[sp] = 1; state[sp] = 0; ordn = 0; while (sp >= 0) { int u = stk[sp]; if (state[sp] == 0) { state[sp] = 1; ord_[ordn++] = u; for (int e = head_[u]; e; e = nxt_[e]) { int v = to_[e]; if (v == par[u]) continue; par[v] = u; stk[++sp] = v; state[sp] = 0; } } else --sp; } } // 计算若在第 t 天种下、到第 D 天累计长高（等差数列 O(1) 求和） // 生长量 g(x) = max(b_i + x*c_i, 1)，随 x 单调（c_i>0 递增、c_i<0 递减）。 // 把 [t,D] 按 g(x) ≥ 1 与否分成两段：一段用等差数列精确求和，另一段按 1 累加。 static long long grow(int i, long long t, long long D) { if (t > D) return 0; long long bi = b[i], ci = c[i]; long long res = 0; if (ci == 0) { long long g = bi < 1 ? 1 : bi; return (D - t + 1) * g; } if (ci > 0) { // b + x*c >= 1 <=> x >= ceil((1-b)/c) long long num = 1 - bi; long long x0 = (num <= 0) ? 0 : (num + ci - 1) / ci; long long lo = max(t, x0), hi = D; // 真实值段 if (lo <= hi) { long long cnt = hi - lo + 1; res += bi * cnt + ci * ((lo + hi) * cnt / 2); } long long lo2 = t, hi2 = min(D, x0 - 1); // 取 1 的段 if (lo2 <= hi2) res += (hi2 - lo2 + 1); } else { // b + x*c >= 1 <=> x <= (b-1)/(-c) long long den = -ci; long long x0 = (bi - 1) / den; long long lo = t, hi = min(D, x0); // 真实值段 if (lo <= hi) { long long cnt = hi - lo + 1; res += bi * cnt + ci * ((lo + hi) * cnt / 2); } long long lo2 = max(t, x0 + 1), hi2 = D; // 取 1 的段 if (lo2 <= hi2) res += (hi2 - lo2 + 1); } return res; } // 判定 D 是否可行（D 至少为 n，否则种不完） static bool feasible(long long D) { if (D < n) return false; static long long lim[MAXN]; for (int i = 1; i <= n; ++i) { // 二分数出最大的 t ∈ [1,D] 使 grow(i,t,D) >= a[i]（grow 随 t 减而增） long long lo = 1, hi = D, best = 0; while (lo <= hi) { long long mid = lo + (hi - lo) / 2; if (grow(i, mid, D) >= a[i]) { best = mid; lo = mid + 1; } else hi = mid - 1; } lim[i] = best; if (best == 0) return false; } // 自底向上收紧父约束 for (int k = ordn - 1; k >= 0; --k) { int u = ord_[k]; if (par[u] && lim[par[u]] > lim[u] - 1) lim[par[u]] = lim[u] - 1; } for (int i = 1; i <= n; ++i) if (lim[i] < 1) return false; // 贪心：按 lim 升序，第 k 个（1-based）需 lim >= k static int idx[MAXN]; for (int i = 1; i <= n; ++i) idx[i] = i; sort(idx + 1, idx + n + 1, [](int x, int y) { return lim[x] < lim[y]; }); for (int k = 1; k <= n; ++k) if (lim[idx[k]] < k) return false; return true; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lld %lld %lld", &a[i], &b[i], &c[i]); ecnt = 0; for (int i = 1; i <= n; ++i) head_[i] = 0; for (int i = 1; i < n; ++i) { int u, v; scanf("%d %d", &u, &v); addEdge(u, v); addEdge(v, u); } buildTree(); long long lo = n, hi = (long long)2e9, ans = hi; // 上界保证可行：取一个足够大的天数（题目保证 1e9 天内可行，用 1e9） hi = (long long)1e9; lo = n; while (lo <= hi) { long long mid = lo + (hi - lo) / 2; if (feasible(mid)) { ans = mid; hi = mid - 1; } else lo = mid + 1; } printf("%lld\n", ans); return 0; }四、代码分段拆解
完整代码在上面，下面按功能分块解释。
头文件与全局变量
先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用，好处是函数之间共享方便，代价是要小心初始化和被意外改写。
#include <cstdio> #include <algorithm> #include <vector>using namespace std; const int MAXN = 100005; const long long INF = (long long)4e18; int n; long long a[MAXN], b[MAXN], c[MAXN]; int head_[MAXN], nxt_[2 * MAXN], to_[2 * MAXN], ecnt; int par[MAXN], ord_[MAXN], ordn; int sp = 0; int u = stk[sp]; int v = to_[e]; long long bi = b[i], ci = c[i]; long long res = 0; long long g = bi < 1 ? 1 : bi; long主体逻辑
主体部分按顺序完成读入、计算、输出。main函数尽量保持线性，把复杂的逻辑拆成独立函数，出问题时更容易定位。
五、实例模拟
光看代码容易虚，用样例实测一遍最踏实。
样例 1
输入：
4 12 1 1 2 4 -1 10 3 0 7 10 -2 1 2 1 3 3 4输出：
5以第一组样例为例，输入是4、12 1 1、2 4 -1、10 3 0、7 10 -2、1 2、1 3、3 4，正确输出是5。建议把这两行数据抄在纸上，用上面的代码手动走一遍，重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西，比看懂代码印象深得多。
六、踩坑总结
最后总结几个要点。
- 左右边界的更新要成对写，边界写错容易死循环
- 判断函数必须是单调的，否则二分不成立
- 高难度题的暴力分很关键，先写一版能过的部分分再想正解
另外提醒一句：这题在 CSP-S 2023 里是提高+/省选-难度，考场上如果没有把握拿满分，先把暴力写法交上去拿到部分分，再回头优化。CSP 是打分制，空着不写才是最亏的。
七、知识点拓展
这题的核心是二分。
二分答案的适用信号是「答案有单调性」。典型问法是「最小/最大是多少」，并且验证一个候选答案比直接求解容易。
建议的练习路径：
- 先把本题独立写一遍，不看代码，遇到卡壳再看提示
- 换个平台提交（ACGO 和洛谷都试试），确保代码在两个平台都能过
- 找两到三道同类型的题练手，巩固这类问题的识别能力
八、适用人群
这道题的适用面：
- 目标是 CSP-S 高分或省选的同学
- 想通过真题理解高难度题如何从暴力优化到正解的同学
- 想弄明白二分类问题标准解法的同学
代码有任何问题欢迎指正，我会及时更新。
关于这个系列
这是「CSP 真题逐题精讲」的第 40 篇。我会按年份从 2019 一路刷到 2025，
CSP-J 和 CSP-S 全覆盖。每篇都给：双平台题号（ACGO + 洛谷）+ 逐行代码拆解 + 真实样例模拟。
跟着刷完这一套，CSP 第一轮的选择题和基础题基本就稳了。
下一篇：CSP-S 2023 消消乐（提高+/省选-）
👉 关注我，不错过后续更新。评论区告诉我你现在刷到哪一年了，我看看能不能按大家的进度调整更新节奏。
