#D0058. 种树 ID: 652 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者:

Hydro 标签> 题目描述 你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。

森林的地图有 nn 片地块，其中 11 号地块连接森林的入口。共有 n-1n−1 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。

你的目标是：在每片地块上均种植一棵树木，并使得 ii 号地块上的树的高度生长到不低于 a_ia i ​ 米。

你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相连）的地块，种一棵高度为 00 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 11 天你只能在 11 号空地种树。

对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 xx 天，ii 号地块上的树会长高 \max(b_i + x \times c_i, 1)max(b i ​ +x×c i ​ ,1) 米。注意这里的 xx 是从整个任务的第一天，而非种下这棵树的第一天开始计算。

你想知道：最少需要多少天能够完成你的任务？

输入格式 输入的第一行包含一个正整数 nn，表示森林的地块数量。

接下来 nn 行：每行包含三个整数 a_i, b_i, c_ia i ​ ,b i ​ ,c i ​ ，分别描述一片地块，含义如题目描述中所述。

接下来 n-1n−1 行：每行包含两个正整数 u_i, v_iu i ​ ,v i ​ ，表示一条连接地块 u_iu i ​ 和 v_iv i ​ 的道路。

输出格式 输出一行仅包含一个正整数，表示完成任务所需的最少天数。

输入数据 1 4 12 1 1 2 4 -1 10 3 0 7 10 -2 1 2 1 3 3 4 输出数据 1 5

提示 【样例 1 解释】

第 11 天：在地块 11 种树，地块 11 的树木长高至 22 米。

第 22 天：在地块 33 种树，地块 1, 31,3 的树木分别长高至 5, 35,3 米。

第 33 天：在地块 44 种树，地块 1, 3, 41,3,4 的树木分别长高至 9, 6, 49,6,4 米。

第 44 天：在地块 22 种树，地块 1, 2, 3, 41,2,3,4 的树木分别长高至 14, 1, 9, 614,1,9,6 米。

第 55 天：地块 1, 2, 3, 41,2,3,4 的树木分别长高至 20, 2, 12, 720,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 ≤ 10^5,1 ≤ a_i ≤ 10^{18}, 1 ≤ b_i ≤ 10^9,0 ≤ |c_i| ≤ 10^9, 1 ≤ u_i, v_i ≤ n1≤n≤10 5 ,1≤a i ​ ≤10 18 ,1≤b i ​ ≤10 9 ,0≤∣c i ​ ∣≤10 9 ,1≤u i ​ ,v i ​ ≤n。保证存在方案能在 10^910 9 天内完成任务。

T4

特殊性质 A：对于所有 1 ≤ i ≤ n1≤i≤n，均有 c_i = 0c i ​ =0；

特殊性质 B：对于所有 1 ≤ i < n1≤i<n，均有 u_i = iu i ​ =i、v_i = i + 1v i ​ =i+1；

特殊性质 C：与任何地块直接相连的道路均不超过 22 条；

特殊性质 D：对于所有 1 ≤ i < n1≤i<n，均有 u_i = 1u i ​ =1。

进入在线编程模式 (Alt+E) 递交 讨论 (0) 题解 (0) 文件 统计 复制 状态 评测队列 服务状态 开发 开源 支持 帮助 联系我们 关于 关于 隐私 服务条款 版权申诉 Language 兼容模式 主题 Worker 0, 91msPowered by Hydro v5.0.0-beta.18 Community