A35528. 种树（tree）
题目描述
种树（tree）
题目描述
你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。
森林的地图有n片地块，其中1号地块连接森林的入口。共有n−1条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。
你的目标是：在每片地块上均种植一棵树木，并使得i号地块上的树的高度生长到不低于ai米。
你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相.连）的地块，种一棵高度为0米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第1天你只能在1号空地种树。
对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第x天，i号地块上的树会长高max(bi+x∗ci,1)
米。注意这里的x是从整个任务的第一天，而非种下这棵树的第一天开始计算。
你想知道：最少需要多少天能够完成你的任务？
输入格式
从文件tree.in中读入数据。
输入的第一行包含一个正整数n，表示森林的地块数量。
接下来n行：每行包含三个整数ai,bi,ci，分别描述一片地块，含义如题目描述中所述。
接下来n−1行：每行包含两个正整数ui,vi，表示一条连接地块ui和vi的道路。
输出格式
输出到文件tree.out中。
输出一行仅包含一个正整数，表示完成任务所需的最少天数。
样例1输入
4
12 1 1
2 4 ‐1
10 3 0
7 10 ‐2
1 2
1 3
3 4
样例1输出
1 5
样例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≤n≤105，1≤ai≤1018,1≤bi≤109，0≤|ci|≤109，1≤ui,vi≤n。保证存在方案能在109天内完成任务
特殊性质A：对于所有1≤i≤n，均有ci=0；
特殊性质B：对于所有1≤i<n，均有ui=i，vi=i+1；
特殊性质C：与任何地块直接相连的道路均不超过2条；
特殊性质D：对于所有1≤i<n，均有ui=1。
参考答案
#include<bits/stdc++.h>
using namespace std;
int n,head[100010],tot,F[100010];
bool v[100010];
vector<pair<int,int> > q;
struct node
{
int to,nex;
} edge[200000];
struct node1
{
long long a,b,c,t;
} a[100010];
void add(int x,int y)
{
edge[++tot].nex=head[x];
edge[tot].to=y;
head[x]=tot;
}
bool Check(int id,int l,int r)
{
if(a[id].c>=0)
{
__int128 h=(__int128)(a[id].b+l*a[id].c+a[id].b+r*a[id].c)*(r-l+1)/2;
if(h>=a[id].a)
return 1;
return 0;
}
if(l>(1-a[id].b)/a[id].c)
{
if(r-l+1>=a[id].a)
return 1;
return 0;
}
if(r<=(1-a[id].b)/a[id].c)
{
__int128 h=(__int128)(a[id].b+l*a[id].c+a[id].b+r*a[id].c)*(r-l+1)/2;
if(h>=a[id].a)
return 1;
return 0;
}
int t=(1-a[id].b)/a[id].c;
__int128 h=(__int128)(a[id].b+l*a[id].c+a[id].b+t*a[id].c)*(t-l+1)/2+r-t;
if(h>=a[id].a)
return 1;
return 0;
}
int work(int id,int x)
{
int l=0,r=x;
while(l+1<r)
{
int mid=(l+r)/2;
if(Check(id,mid,x))
l=mid;
else
r=mid;
}
if(Check(id,r,x))
return r;
return l;
}
bool check(int x)
{
q.clear();
for(int i=1;i<=n;i++)
{
int jl=work(i,x);
if(jl==0)
return 0;
q.push_back(make_pair(jl,i));
}
sort(q.begin(),q.end());
memset(v,0,sizeof v);
v[0]=1;
int now=0;
for(int i=0;i<q.size();i++)
{
int id=q[i].second;
while(!v[id])
{
now++;
v[id]=1;
id=F[id];
}
if(now>q[i].first)
return 0;
}
return 1;
}
void dfs(int x,int fa)
{
F[x]=fa;
for(int i=head[x];i;i=edge[i].nex)
{
if(edge[i].to==fa)
continue;
dfs(edge[i].to,x);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&a[i].a,&a[i].b,&a[i].c);
for(int i=1;i<n;i++)
{
int U,V;
scanf("%d%d",&U,&V);
add(U,V);
add(V,U);
}
dfs(1,0);
int l=1,r=1e9;
while(l+1<r)
{
int mid=(l+r)/2;
if(check(mid))
r=mid;
else
l=mid;
}
if(check(l))
printf("%d",l);
else
printf("%d",r);
return 0;
}