迟来的补题
本题是让最小化所有树长到指定高度日期的最大值，于是想到二分答案。
那么，对于一个给定的期限\(x\)，如何判断是否能在这个日期内完成任务呢？
首先我们发现前\(n\)天每天都要种树，那么假设我们已经知道了每个地块最晚哪个日期种树，能保证在期限\(x\)之内长到指定高度，我们就可以贪心地选择：把每个地块的最晚日期数组\(late\)从小到大排序，依次选择每一个元素：
- 如果该元素已经被选择了，就什么操作也不做。
- 如果该元素还没被选择，就先把祖先节点中没有被选择过的选择上（因为要在一个地块种树，必须先在它的祖先种树），每种一棵树\(tim+1\)。
每个元素\(i\)选完后，判断\(tim\)和\(late_i\)的大小关系，如果\(tim>late_i\)，说明当前这棵树已经种晚了，返回false。
为什么这样贪心地选日期要求最早（种树需求最紧迫）的，正确性就能得到保证呢？
我们考虑\(2\)个地块，第\(1\)个地块最晚种树日期\(<\)第\(2\)个地块，这说明第\(1\)个地块种树的需求更紧迫。按照贪心的思想，我们先选第\(1\)个，那么必须把它的祖先地块全都种上树，再考虑第\(2\)个。如果我们先选第\(2\)个地块种上树，那么选第\(1\)个地块时，仍然避免不了要先在它的祖先地块上种树。因此后者不一定能得到最优答案。
现在还有\(1\)个问题：如何求\(late\)数组？
这就跟输入的\(b,c\)有关系了。我们知道第\(j\)天第\(i\)棵树会生长\(\max\{b_i+c_i\times j,1\}\)米，因此我们要找的\(late_i\)，就是（\(x\)表示日期限制）：
\[\large{\max\limits_{\sum\limits_{j=k}^x \max\{b_i+c_i\times j,1\}\ge a_i}k} \]我们可以\(O(1)\)求出\(\sum\limits_{j=k}^x b_i+c_i\times j\)，因此可以二分求出\(k\)作为\(late_i\)。
具体怎么求呢？我们设\(\sum\limits_{j=l}^r b_x+c_x\times j\)为\(f(l,r,x)\)。
计算\(f(l,r,x)\)，可以对\(c_x\)的值进行分类讨论。
如果\(c_x\ge 0\)，那么我们完全不需要考虑和\(1\)取\(\max\)，直接套用等差数列求和公式即可：
\[(r-l+1)\times b_x+(l+r)\times \frac{r-l+1}{2}\times c_x \]如果\(c_x<0\)，我们解一个不等式，得到第几项开始值\(<1\)，再分成两部分分别计算，再求和。
\[b_x+c_x\times k<1\\ k>\frac{1-b_x}{c_x}\]故两部分分别是：
- \(j\in [l,k]:\quad b_x+c_x\times j\ge 1\)
求和：\((k-l+1)\times b+\frac{(l+k)\times(k-l+1)}{2}\times c\) - \(j\in [k+1,r]:\quad b_x+c_x\times j<1\)
求和：\(r-k\)
注意这里只给出了\(k\in[l,r)\)的情况，代码实现需要注意特判只有一个部分的情况，可以结合代码理解。
时间复杂度：(二分)套(二分+排序)，外层二分\(O(\log V)\)（\(V\)是值域\(10^9\)），内层\(O(n\log n)\)，总共\(O(n\log V\log n)\)。
注意：
- \(f()\)计算出的值可能超出
long long，需要开__int128。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
int n,a[N],b[N],c[N],k[N],late[N],fa[N],pos[N];
bool vis[N];
vector<int> G[N];
__int128 calc(int l,int r,int x){//第x棵树在[l,r]天能长到多少
if(c[x]>=0) return (__int128)(r-l+1)*b[x]+(__int128)(l+r)*(r-l+1)/2*c[x];
if(k[x]<l) return r-l+1;//只有右边
if(k[x]>=r) return (__int128)(r-l+1)*b[x]+(__int128)(l+r)*(r-l+1)/2*c[x];//只有左边
return (__int128)(r-k[x])+(__int128)(k[x]-l+1)*b[x]+(__int128)(l+k[x])*(k[x]-l+1)/2*c[x];
}
void dfs(int u,int f){
fa[u]=f;
for(int i:G[u])
if(i!=f) dfs(i,u);
}
bool cmp(int a,int b){return late[a]<late[b];}
int cnt;
bool check(int x){//x天能否完成
for(int i=1;i<=n;i++){//二分找每个位置最晚种树时间
int l=1,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(calc(mid,x,i)>=a[i]) l=mid;
else r=mid-1;
}
if(l>x) return 0;
pos[i]=i,late[i]=l;
}
sort(pos+1,pos+1+n,cmp);
int tim=0;
memset(vis,0,sizeof vis);
vis[0]=1;//不加下面会死循环
for(int i=1;i<=n;i++){
for(int j=pos[i];!vis[j];j=fa[j])
vis[j]=1,tim++;
if(tim>late[pos[i]]) return 0;
}
return 1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
if(c[i]<0) k[i]=(1-b[i])/c[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
dfs(1,0);
int l=n,r=1e9;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<"\n";
return 0;
}