题库 NOIP CSP J/S信奥赛 题目列表 种树(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。

题目信息
提高组 复赛 2023 编程题
-
正确率
0
评论
392
点击
QQ
公众号
客服
扫一扫