二分完成天数；固定 D 时用求根公式 O(1) 算出每棵树的最晚种下日，再把子树截止时间下压成压缩截止日，按升序排日程即可判定。
OJ: roj
题目 ID: 3679
难度:提高+/省选-
标签:二分答案树贪心数学python
创建: 2026-10-02 15:14
更新: 2026-10-10 11:30
形式化题目
给定
- 第
天必须在 号点种下一棵高 的树；之后每天选一个未种且与已种地块相邻（单条边相连）的地块种树，直到 天全部种完。 - 第
天（绝对天数，从第 天起算）地块 的树长高 ，从种下当天开始累计。
求最小的
样例 1：下图是样例的树形结构，节点标签给出各点的
graph TD
n1["1: a=12 b=1 c=1"]
n2["2: a=2 b=4 c=-1"]
n3["3: a=10 b=3 c=0"]
n4["4: a=7 b=10 c=-2"]
n1 --- n2
n1 --- n3
n3 --- n4
一种 5 天完成的方案（与题面样例解释一致），表格逐天记录种植动作与当天生长后的累计高度：
| 天 | 当天种植 | 1 号 | 2 号 | 3 号 | 4 号 |
|---|---|---|---|---|---|
| 1 | 1 号 | 2 | — | — | — |
| 2 | 3 号 | 5 | — | 3 | — |
| 3 | 4 号 | 9 | — | 6 | 4 |
| 4 | 2 号 | 14 | 1 | 9 | 6 |
| 5 | （已种完，只生长） | 20 | 2 | 12 | 7 |
第 5 天四棵树分别达到
正解
思路
朴素做法与瓶颈。 固定天数
第一步：把顺序拆成每棵树自己的"最晚种下日"。 第
每天生长量都不小于
若从第
令
：每天固定长 ， ； ：每项都是 ， ，解二次不等式取较小根向上取整； ：记 ，第 天之后每天只长 ；尾段按 米直接累加，不足时对线性段 同样解二次方程。
第二步：合法顺序就是树的拓扑序。 已种集合始终是含
第三步：截止时间要沿祖先链下压。 只按各点自己的
取最紧的一个，定义压缩截止时间（子树内最紧的后代截止被"下压"到
第四步：判定定理。 把
- 必要性：任何合法日程中每个点都满足
（上式对每个后代 成立，取最紧的即得）。 最小的 个点需要 个互不相同的天数，且每个都不超过 ，这些天只能取自 ，故 。 - 充分性：按
升序把第 个点安排在第 天。祖先的 严格小于后代（深度多 、取 min 的范围只缩不扩），所以这个顺序天然父先于子；又 ，截止也满足； 天恰好各用一次。 号点的 最小（深度 且取全树 min），总是排第 天，与"第 天只能种 号点"吻合。
在样例上分别代入
| 点 | 深度 |
||||
|---|---|---|---|---|---|
| 1 | 0 | 2 | 0 | 3 | 1 |
| 2 | 1 | 3 | 3 | 4 | 4 |
| 3 | 1 | 1 | 1 | 2 | 2 |
| 4 | 2 | 2 | 2 | 3 | 3 |
第五步：二分答案。
代码
cpp
/**
* 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-10-10 11:30
* update_at: 2026-10-10 11:30
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>a,b,c; vector<vector<int> > children; vector<int> depthv, orderv;
ll isqrt_ll(__int128 x){ long double y=(long double)x; ll r=sqrt(y); while((__int128)(r+1)*(r+1)<=x) r++; while((__int128)r*r>x) r--; return r;}
ll ceil_div(ll x,ll y){return (x+y-1)/y;}
ll min_grow_days(ll aa,ll bb,ll cc,ll D){ if(cc==0) return ceil_div(aa,bb); ll q=-cc; if(cc>0 || (bb-1)/q>=D){ ll B=2*bb+cc*(2*D+1); if(cc>0){ __int128 delta=(__int128)B*B-(__int128)8*cc*aa; if(delta<0) return D+1; ll sq=isqrt_ll(delta); ll m=(B-sq+2*cc-1)/(2*cc); while(m>1 && (__int128)B*(m-1)-(__int128)cc*(m-1)*(m-1)>=2*(__int128)aa) m--; while(m<=D && (__int128)B*m-(__int128)cc*m*m<2*(__int128)aa) m++; return m;} ll m=max((isqrt_ll((__int128)B*B+(__int128)8*q*aa)-B+2*q-1)/(2*q),1LL); while(m<=D && (__int128)B*m+(__int128)q*m*m<2*(__int128)aa) m++; return m; }
ll k=(bb-1)/q, m0=D-k; if(aa<=m0) return aa; if(k==0) return D+1; ll B2=2*bb+cc*(2*k+1); ll nn=max((isqrt_ll((__int128)B2*B2+(__int128)8*q*(aa-m0))-B2+2*q-1)/(2*q),1LL); while(nn<=k && (__int128)B2*nn+(__int128)q*nn*nn<2*(__int128)(aa-m0)) nn++; return nn+m0;}
bool feasible(ll D){int n=a.size(); vector<ll> t(n),mv(n); for(int i=0;i<n;i++){ll mm=min_grow_days(a[i],b[i],c[i],D); if(mm>D) return false; t[i]=D-mm+1;} for(int idx=(int)orderv.size()-1;idx>=0;idx--){int u=orderv[idx]; ll best=t[u]-depthv[u]; for(int j=0;j<(int)children[u].size();j++) if(mv[children[u][j]]<best) best=mv[children[u][j]]; mv[u]=best;} vector<ll> rankv(n); for(int u=0;u<n;u++) rankv[u]=depthv[u]+mv[u]; sort(rankv.begin(),rankv.end()); for(int j=0;j<n;j++) if(rankv[j]<j+1) return false; return true;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n; if(!(cin>>n)) return 0; a.resize(n); b.resize(n); c.resize(n); for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i]; vector<vector<int> > g(n); for(int i=0;i<n-1;i++){int u,v;cin>>u>>v;u--;v--;g[u].push_back(v);g[v].push_back(u);} vector<int> parent(n,-1), st; depthv.assign(n,0); children.assign(n,vector<int>()); parent[0]=-2; st.push_back(0); while(!st.empty()){int u=st.back();st.pop_back(); orderv.push_back(u); for(int i=0;i<(int)g[u].size();i++){int v=g[u][i]; if(parent[v]==-1){parent[v]=u; depthv[v]=depthv[u]+1; children[u].push_back(v); st.push_back(v);}}} ll lo=1,hi=1000000000LL; while(lo<hi){ll mid=(lo+hi)/2; if(feasible(mid)) hi=mid; else lo=mid+1;} cout<<lo<<'\n'; return 0;}python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://roj.ac.cn https://rbook.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 15:19
# update_at: 2026-10-02 15:19
import sys
from math import isqrt
def min_grow_days(a: int, b: int, c: int, D: int) -> int:
"""固定 D 天完成时，这棵树最少要连续生长几天（含种下当天）；返回值大于 D 表示做不到。
第 x 天长高 max(b + x*c, 1)，连续生长 m 天（第 D-m+1 天种下）的总高度 S(m) 随 m 递增，
这里直接解 S(m) >= a 的最小 m，避免对每个 D 再套一层二分。
"""
if c == 0:
return -(-a // b) # 每天固定长 b 米，向上取整
q = -c
if c > 0 or (b - 1) // q >= D:
# [1, D] 内每天生长量 b + x*c 都不小于 1：S(m) = (B*m - c*m*m)/2
B = 2 * b + c * (2 * D + 1)
if c > 0:
delta = B * B - 8 * c * a
if delta < 0:
return D + 1 # 二次函数始终低于 a，从第 1 天种也长不到
# 2S(m) >= 2a 即 c*m^2 - B*m + 2a <= 0，最小 m 是较小根向上取整
m = (B - isqrt(delta) + 2 * c - 1) // (2 * c) # 根的上界，再向下校准
while m > 1 and B * (m - 1) - c * (m - 1) * (m - 1) >= 2 * a:
m -= 1
while m <= D and B * m - c * m * m < 2 * a:
m += 1
return m
# c < 0 但整段都线性：q*m^2 + B*m >= 2a，取较大根向上取整
m = max((isqrt(B * B + 8 * q * a) - B + 2 * q - 1) // (2 * q), 1)
while m <= D and B * m + q * m * m < 2 * a:
m += 1
return m
# c < 0：第 k 天之后生长量掉到 1，前段线性、后段按 1 米计
k = (b - 1) // q # 最后一个满足 b + x*c >= 1 的天
m0 = D - k # 尾部按 1 米生长的天数
if a <= m0:
return a # 只靠尾段每天 1 米就够
if k == 0:
return D + 1 # 全程每天只长 1 米，a > D 时完不成
# 设线性段长 n = m - m0，2(S - m0) = B2*n + q*n*n，解较大根
B2 = 2 * b + c * (2 * k + 1)
n = max((isqrt(B2 * B2 + 8 * q * (a - m0)) - B2 + 2 * q - 1) // (2 * q), 1)
while n <= k and B2 * n + q * n * n < 2 * (a - m0):
n += 1
return n + m0
def feasible(D: int, a: list[int], b: list[int], c: list[int],
children: list[list[int]], depth: list[int], order: list[int]) -> bool:
"""判断能否在第 D 天完成：先算每棵树最晚种下日 t，再检查全树可行的种植日程。"""
n = len(a)
t = [0] * n
for i in range(n):
m = min_grow_days(a[i], b[i], c[i], D)
if m > D:
return False # 这棵树在 D 天内长不到 a_i
t[i] = D - m + 1 # 最晚种下日
# T[u] = depth[u] + 子树内 min(t[w] - depth[w])：祖先必须不晚于它，后代才能全部赶上
mv = [0] * n
for u in reversed(order): # 后序：孩子的 mv 已经算好
best = t[u] - depth[u]
for v in children[u]:
if mv[v] < best:
best = mv[v]
mv[u] = best
# 全部 n 个 T 升序排成日程：第 j 个必须能排在第 j 天（T 升序天然是先祖先的拓扑序）
rank = sorted(depth[u] + mv[u] for u in range(n))
return all(val >= j for j, val in enumerate(rank, 1))
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
a = [0] * n
b = [0] * n
c = [0] * n
for i in range(n):
a[i], b[i], c[i] = next(data), next(data), next(data)
g: list[list[int]] = [[] for _ in range(n)]
for _ in range(n - 1):
u, v = next(data) - 1, next(data) - 1
g[u].append(v)
g[v].append(u)
# 以 1 号点为根：先序（父在子前）+ 深度 + 子女表，迭代写法避开十万层递归
parent = [-1] * n
depth = [0] * n
children: list[list[int]] = [[] for _ in range(n)]
order: list[int] = []
stack = [0]
parent[0] = -2 # 根标记为已访问
while stack:
u = stack.pop()
order.append(u)
for v in g[u]:
if parent[v] == -1:
parent[v] = u
depth[v] = depth[u] + 1
children[u].append(v)
stack.append(v)
lo, hi = 1, 10**9 # 题面保证 1e9 天内存在方案
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid, a, b, c, children, depth, order):
hi = mid
else:
lo = mid + 1
print(lo)
if __name__ == "__main__":
solve()复杂度
- 时间：二分约
轮，每轮 求各点 、 一次后序取子树 min、 排序，合计 ； ，实测最大测例约 （本地单测例限时 ，20 组真实数据全部 PASS；OJ 限时 对 Python 偏紧）。 - 空间：
存树与三个数组，实测峰值约 （ 达 、求根判别式到 量级，Python 整数免溢出；C++ 中需用 __int128或比较前先做溢出保护，其余做法相同）。
总结
- 固定
后"早种不亏"，每棵树有独立的最晚种下日 ； 是分段二次且随 递增，用求根公式 解出，避免二分套二分。 - 合法种植顺序恰是树的拓扑序（父先于子）；点
的真实截止被全子树下压为 。 - 判定定理：
升序第 个排第 天可行 对所有 成立；必要性是鸽笼，充分性给出显式日程（ 升序天然是拓扑序）。 - 边界：
时判定退化为 ； 时生长量会掉到 ，按尾段处理；任一棵在第 天种也达不到 时该 立即判负。 - 验证：样例输出
，仓库 20 组真实测试数据（ tree1–tree20）输出全部一致。
