[CSP-S 2023] 种树

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

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

OJ: luogu

题目 ID: P9755

难度:提高+/省选-

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

日期: 2026-07-06 08:46

题意

有一棵以 1 号点连接入口的树。每天最多种一棵树，且只能在已经种树地块的相邻空地种树，所以在以 1 为根后，每个点必须在父亲之后种下。

如果第 i 个点在第 d 天种下，到第 T 天时，它获得的总高度为：

text

1sum_{x=d..T} max(b_i + x*c_i, 1)

要求所有点高度都不低于 $a_i$ ，求最小完成天数 T。

思路

小数据可以二分 T，然后递归枚举所有合法的连通种植顺序：

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// brute.cpp：小数据暴力解，二分天数后递归枚举所有合法的连通种植顺序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;

int n;
long long need_h[MAXN], b[MAXN], c[MAXN];
bool edge[MAXN][MAXN];
int deadline_day[MAXN];
bool planted[MAXN];

__int128 sum_linear(long long bb, long long cc, long long l, long long 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;
}

__int128 growth_sum(int u, long long l, long long r) {
    if (l > r) return 0;
    if (c[u] >= 0) return sum_linear(b[u], c[u], l, r);
    long long dec = -c[u];
    long long last_big = (b[u] - 1) / dec;
    long long 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;
}

int calc_deadline(int u, long long total_day) {
    if (growth_sum(u, 1, total_day) < need_h[u]) return 0;
    long long left = 1, right = total_day;
    while (left < right) {
        long long 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 (int)left;
}

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;
}

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;
}

bool check(long long 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;
    }

    long long left = 1, right = 200;
    while (!check(right)) {
        right *= 2;
    }
    while (left < right) {
        long long mid = (left + right) / 2;
        if (check(mid)) right = mid;
        else left = mid + 1;
    }
    cout << left << '\n';
    return 0;
}

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

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

text

1sum_{x=deadline[i]..T} max(b_i + x*c_i, 1) >= 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// main.cpp：二分完成天数，把每个点转成最晚种植日，再做树上 EDF 调度。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long need_h[MAXN], b[MAXN], c[MAXN];
vector<int> g[MAXN], child[MAXN];
int deadline_day[MAXN];
int min_subtree_deadline[MAXN];
vector<int> order_nodes;

__int128 sum_linear(long long bb, long long cc, long long l, long long 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;
}

__int128 growth_sum(int u, long long l, long long r) {
    if (l > r) {
        return 0;
    }
    if (c[u] >= 0) {
        return sum_linear(b[u], c[u], l, r);
    }

    long long dec = -c[u];
    long long last_big = (b[u] - 1) / dec; // x <= last_big 时 b-c*x 至少为 1
    long long 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;
}

int calc_deadline(int u, long long total_day) {
    if (growth_sum(u, 1, total_day) < need_h[u]) {
        return 0;
    }

    long long left = 1;
    long long right = total_day;
    while (left < right) {
        long long 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 (int)left;
}

bool check(long long 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;
        }
    }

    for (int i = (int)order_nodes.size() - 1; i >= 0; i--) {
        int u = order_nodes[i];
        min_subtree_deadline[u] = deadline_day[u];
        for (int j = 0; j < (int)child[u].size(); j++) {
            int v = child[u][j];
            min_subtree_deadline[u] = min(min_subtree_deadline[u], min_subtree_deadline[v]);
        }
    }

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(min_subtree_deadline[1], 1));

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

    return true;
}

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);
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent[u]) {
                continue;
            }
            parent[v] = u;
            child[u].push_back(v);
            q.push(v);
        }
    }
}

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();

    long long left = 1;
    long long right = 1000000000LL;
    while (left < right) {
        long long 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$ 。