[CSP-S 2023] 种树

GitHub跳转原题关系图返回列表

二分完成天数，把每个点转成最晚种植日，再用最早截止时间优先判断树上调度。

OJ: luogu

题目 ID: P9755

难度:提高+/省选-

标签:二分贪心树形结构优先队列

创建: 2026-07-06 08:46

更新: 2026-10-07 10:45

形式化题目

给定 $n$ 片地块构成的树， $1$ 号地块连接入口。每天可以在与已种树地块相邻的空地上种一棵高度为 $0$ 的树（第 $1$ 天只能种 $1$ 号地块）。

若点 $i$ 在第 $d$ 天种下，则到第 $T$ 天它的高度为

\sum_{x=d}^{T} \max(b_i + x \cdot c_i,\ 1)

（ $x$ 从整个任务的第一天开始计数）。要求所有点高度不低于 $a_i$ ，求最小完成天数 $T$ 。

暴力解法

思路

二分 $T$ ，然后递归枚举所有合法的连通种植顺序：第 day 天在"未种、且与某种下的地块相邻"的地块里任选一个种下，检查每个点种下时是否不晚于自己的最晚种植日。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-06 08:46
 * update_at: 2026-10-01 22:33
 */
// brute.cpp：小数据暴力解，二分天数后递归枚举所有合法的连通种植顺序。
// 只适合 n <= 10 左右的小数据，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 12;

int n;
ll need_h[MAXN]; // 目标高度 a[i]
ll b[MAXN];      // 每天长高 b[i] + x*c[i] 的截距
ll c[MAXN];      // 每天长高的斜率，可为负
bool edge[MAXN][MAXN]; // 邻接矩阵
ll deadline_day[MAXN]; // deadline_day[i]：点 i 的最晚种植日
bool planted[MAXN];    // planted[i]：点 i 是否已经种下

// 等差数列求和：sum_{x=l..r} (bb + cc*x)，用 __int128 防溢出
__int128 sum_linear(ll bb, ll cc, ll l, ll r) {
    if (l > r) return 0;
    __int128 cnt = (__int128)r - l + 1;
    __int128 sum_x = (__int128)(l + r) * cnt / 2;
    return (__int128)bb * cnt + (__int128)cc * sum_x;
}

// 点 u 在第 l..r 天的总生长量：sum_{x=l..r} max(b + x*c, 1)
__int128 growth_sum(int u, ll l, ll r) {
    if (l > r) return 0;
    if (c[u] >= 0) return sum_linear(b[u], c[u], l, r);
    ll dec = -c[u];
    ll last_big = (b[u] - 1) / dec;
    ll mid = min(r, last_big);
    __int128 result = 0;
    if (l <= mid) result += sum_linear(b[u], c[u], l, mid);
    if (mid + 1 <= r) result += (__int128)r - (mid + 1) + 1;
    return result;
}

// 二分点 u 的最晚种植日，不够种返回 0，超过 n 天封顶为 n
ll calc_deadline(int u, ll total_day) {
    if (growth_sum(u, 1, total_day) < need_h[u]) return 0;
    ll left = 1, right = total_day;
    while (left < right) {
        ll mid = (left + right + 1) / 2;
        if (growth_sum(u, mid, total_day) >= need_h[u]) left = mid;
        else right = mid - 1;
    }
    if (left > n) return n;
    return left;
}

// 点 u 现在能不能种：要么是入口 1，要么有已经种好的邻居
bool has_planted_neighbor(int u) {
    if (u == 1) return true;
    for (int v = 1; v <= n; v++) {
        if (edge[u][v] && planted[v]) {
            return true;
        }
    }
    return false;
}

// 枚举第 day 天种哪棵树；能铺满 1..n 天就找到了合法顺序
bool dfs_order(int day) {
    if (day == n + 1) {
        return true;
    }
    for (int u = 1; u <= n; u++) {
        if (!planted[u] && has_planted_neighbor(u) && day <= deadline_day[u]) {
            planted[u] = true;
            if (dfs_order(day + 1)) {
                return true;
            }
            planted[u] = false;
        }
    }
    return false;
}

// 判断完成天数 total_day 是否可行
bool check(ll total_day) {
    if (total_day < n) return false;
    for (int i = 1; i <= n; i++) {
        deadline_day[i] = calc_deadline(i, total_day);
        if (deadline_day[i] == 0) return false;
        planted[i] = false;
    }
    return dfs_order(1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> need_h[i] >> b[i] >> c[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edge[u][v] = edge[v][u] = true;
    }

    // 先倍增找上界，再二分最小完成天数
    ll left = 1, right = 200;
    while (!check(right)) {
        right *= 2;
    }
    while (left < right) {
        ll mid = (left + right) / 2;
        if (check(mid)) right = mid;
        else left = mid + 1;
    }
    cout << left << '\n';
    return 0;
}

复杂度

时间： $O(\log T \cdot n!)$ 级别，枚举所有合法种植顺序
空间： $O(n)$

瓶颈

枚举量阶乘级增长，只能处理 $n \leqslant 10$ 左右的小数据。

正解

思路

满分做法仍然二分答案，但检查 $T$ 时不能枚举顺序。

固定一个完成天数 $T$ 。对每个点 $i$ ，二分出它的最晚种植日 $deadline[i]$ ：

\sum_{x=deadline[i]}^{T} \max(b_i + x \cdot c_i,\ 1) \geqslant a_i

如果从第 $1$ 天种到第 $T$ 天都达不到 $a_i$ ，那么这个 $T$ 一定不可行。

接下来问题变成：

text

1
2
3在树上安排每天种一个点；
父亲必须早于儿子；
每个点必须不晚于自己的 deadline 被种下。

这个调度可以用贪心判断，但优先级不能只看当前点自己的 deadline。如果某个点本身不急，但它的子树里有很急的后代，就应该尽早种它来打开这条分支。

所以对每个点 $u$ 计算：

text

1min_deadline[u] = u 的子树里最小的 deadline

每天把当前已经可种的点放进优先队列，优先种 min_deadline 最小的点。这样会优先打开包含紧急节点的子树。种下某个点时，再检查它自己的 deadline 是否已经过期；如果过期，当前 $T$ 不可行。

计算某个点从 $d$ 到 $T$ 的生长量时，要处理 $c_i < 0$ 的情况。因为每天至少长高 $1$ ，所以把区间分成两段：

$b_i + x \cdot c_i \geqslant 1$ 的部分，用等差数列求和；
后面不足 $1$ 的部分，每天按 $1$ 计算。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-06 08:46
 * update_at: 2026-10-01 22:33
 */
// main.cpp：二分完成天数，把每个点转成最晚种植日，再做树上 EDF 调度。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n;
ll need_h[MAXN]; // 目标高度 a[i]
ll b[MAXN];      // 每天长高 b[i] + x*c[i] 的截距
ll c[MAXN];      // 每天长高的斜率，可为负

vector<int> g[MAXN];    // 原树邻接表
vector<int> child[MAXN]; // 以 1 为根的有根树的孩子表
ll deadline_day[MAXN];   // deadline_day[i]：点 i 的最晚种植日
ll min_subtree_deadline[MAXN]; // 子树内最小的 deadline，做 EDF 优先级
vector<int> order_nodes; // BFS 序，倒着遍历就是自底向上
int order_cnt;           // order_nodes 的长度，避免 size() 强转

// 等差数列求和：sum_{x=l..r} (bb + cc*x)
// 值域到 1e27 量级，用 __int128 防溢出（GCC 扩展，OJ 常用）。
__int128 sum_linear(ll bb, ll cc, ll l, ll r) {
    if (l > r) {
        return 0;
    }
    __int128 cnt = (__int128)r - l + 1;
    __int128 sum_x = (__int128)(l + r) * cnt / 2;
    return (__int128)bb * cnt + (__int128)cc * sum_x;
}

// 点 u 在第 l..T 天的总生长量：sum_{x=l..r} max(b + x*c, 1)
// c < 0 时把区间切成两段：b + x*c >= 1 的部分等差求和，后面每天按 1 算。
__int128 growth_sum(int u, ll l, ll r) {
    if (l > r) {
        return 0;
    }
    if (c[u] >= 0) {
        return sum_linear(b[u], c[u], l, r);
    }

    ll dec = -c[u];
    ll last_big = (b[u] - 1) / dec; // x <= last_big 时 b + x*c 至少为 1
    ll mid = min(r, last_big);
    __int128 result = 0;
    if (l <= mid) {
        result += sum_linear(b[u], c[u], l, mid);
    }
    if (mid + 1 <= r) {
        result += (__int128)r - (mid + 1) + 1;
    }
    return result;
}

// 二分点 u 的最晚种植日：最小的 d 满足 sum(d..T) >= a[u]。
// 种到第 1 天都不够就返回 0；超过 n 天没意义，封顶为 n。
ll calc_deadline(int u, ll total_day) {
    if (growth_sum(u, 1, total_day) < need_h[u]) {
        return 0;
    }

    ll left = 1;
    ll right = total_day;
    while (left < right) {
        ll mid = (left + right + 1) / 2;
        if (growth_sum(u, mid, total_day) >= need_h[u]) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    if (left > n) {
        return n;
    }
    return left;
}

// 判断完成天数 total_day 是否可行：
// 每天种一个点、父亲早于儿子、每个点不晚于自己的 deadline。
bool check(ll total_day) {
    if (total_day < n) {
        return false;
    }

    for (int i = 1; i <= n; i++) {
        deadline_day[i] = calc_deadline(i, total_day);
        if (deadline_day[i] == 0) {
            return false;
        }
    }

    // 自底向上求每棵子树里最小的 deadline
    for (int i = order_cnt - 1; i >= 0; i--) {
        int u = order_nodes[i];
        min_subtree_deadline[u] = deadline_day[u];
        int child_cnt = child[u].size();
        for (int j = 0; j < child_cnt; j++) {
            int v = child[u][j];
            min_subtree_deadline[u] = min(min_subtree_deadline[u], min_subtree_deadline[v]);
        }
    }

    // 每天在"可种的点"里种 min_subtree_deadline 最小的，
    // 优先打开包含紧急节点的子树；种下时检查自己的 deadline 有没有过期。
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > heap;
    heap.push(make_pair(min_subtree_deadline[1], 1));

    for (int day = 1; day <= n; day++) {
        if (heap.empty()) {
            return false;
        }
        int u = heap.top().second;
        heap.pop();
        if (deadline_day[u] < day) {
            return false;
        }
        int child_cnt = child[u].size();
        for (int j = 0; j < child_cnt; j++) {
            int v = child[u][j];
            heap.push(make_pair(min_subtree_deadline[v], v));
        }
    }

    return true;
}

// 以 1 为根 BFS 建有根树，同时记录 BFS 序
void build_rooted_tree() {
    vector<int> parent(n + 1, 0);
    queue<int> q;
    parent[1] = -1;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order_nodes.push_back(u);
        int adj_cnt = g[u].size();
        for (int i = 0; i < adj_cnt; i++) {
            int v = g[u][i];
            if (v == parent[u]) {
                continue;
            }
            parent[v] = u;
            child[u].push_back(v);
            q.push(v);
        }
    }
    order_cnt = order_nodes.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> need_h[i] >> b[i] >> c[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    build_rooted_tree();

    // 二分答案：保证 1e9 天内有解
    ll left = 1;
    ll right = 1000000000LL;
    while (left < right) {
        ll mid = (left + right) / 2;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    cout << left << '\n';
    return 0;
}

复杂度

二分答案需要 $O(\log 10^9)$ 次检查。

每次检查中，每个点二分一次最晚种植日，复杂度 $O(n \log T)$ ；调度优先队列复杂度 $O(n \log n)$ 。

总时间复杂度 $O(\log 10^9 \cdot (n \log T + n \log n))$ ，空间复杂度 $O(n)$ 。

总结

本题的关键是把"最后高度是否足够"转成每个点的最晚种植日。之后它就变成一个带树上先后约束的截止日期调度问题。

固定答案后，按子树最早截止时间优先的贪心负责判断是否能排出合法种植顺序；外层二分负责找到最小完成天数。

P9755 [CSP-S 2023] 种树

题目描述

你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。

森林的地图有 $n$ 片地块，其中 $1$ 号地块连接森林的入口。共有 $n-1$ 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。

你的目标是：在每片地块上均种植一棵树木，并使得 $i$ 号地块上的树的高度生长到不低于 $a_i$ 米。

你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相连）的地块，种一棵高度为 $0$ 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 $1$ 天你只能在 $1$ 号空地种树。

对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 $x$ 天， $i$ 号地块上的树会长高 $\max(b_i + x \times c_i, 1)$ 米。注意这里的 $x$ 是从整个任务的第一天，而非种下这棵树的第一天开始计算。

你想知道：最少需要多少天能够完成你的任务？

输入格式

输入的第一行包含一个正整数 $n$ ，表示森林的地块数量。

接下来 $n$ 行：每行包含三个整数 $a_i, b_i, c_i$ ，分别描述一片地块，含义如题目描述中所述。

接下来 $n-1$ 行：每行包含两个正整数 $u_i, v_i$ ，表示一条连接地块 $u_i$ 和 $v_i$ 的道路。

输出格式

输出一行仅包含一个正整数，表示完成任务所需的最少天数。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例 1 解释】

第 $1$ 天：在地块 $1$ 种树，地块 $1$ 的树木长高至 $2$ 米。

第 $2$ 天：在地块 $3$ 种树，地块 $1, 3$ 的树木分别长高至 $5, 3$ 米。

第 $3$ 天：在地块 $4$ 种树，地块 $1, 3, 4$ 的树木分别长高至 $9, 6, 4$ 米。

第 $4$ 天：在地块 $2$ 种树，地块 $1, 2, 3, 4$ 的树木分别长高至 $14, 1, 9, 6$ 米。

第 $5$ 天：地块 $1, 2, 3, 4$ 的树木分别长高至 $20, 2, 12, 7$ 米。

【样例 2】

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。

【样例 3】

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

【样例 4】

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

【数据范围】

对于所有测试数据有： $1 \le n \le 10^5,1 \le a_i \le 10^{18}, 1 \le b_i \le 10^9,0 \le |c_i| \le 10^9, 1 \le u_i, v_i \le n$ 。保证存在方案能在 $10^9$ 天内完成任务。

::cute-table{tuack}

测试点编号	$n \leq$	特殊性质
$1$	$20$	$\text A$
$2\sim4$	^	无
$5\sim6$	$500$	$\text A$
$7\sim8$	$10^5$	^
$9\sim10$	^	$\text B$
$11\sim13$	^	$\text C$
$14\sim16$	^	$\text D$
$17\sim20$	^	无

特殊性质 $\text A$ ：对于所有 $1 ≤ i ≤ n$ ，均有 $c_i = 0$ ；

特殊性质 $\text B$ ：对于所有 $1 ≤ i < n$ ，均有 $u_i = i,v_i = i + 1$ ；

特殊性质 $\text C$ ：与任何地块直接相连的道路均不超过 $2$ 条；

特殊性质 $\text D$ ：对于所有 $1 ≤ i < n$ ，均有 $u_i = 1$ 。