Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 6221 --4.种树
6221: 4.种树
警告!
题目
状态
题解
题目描述
你是一个森林养护员,有一天,你接到了一个任务:在一片森林内的地块上种树,并养护至树木长到指定的高度。 森林的地图有 $n$ 片地块,其中 $1$ 号地块连接森林的入口。共有 $n-1$ 条道路连接这些地块,使得每片地块都能通过道路互相到达。最开始,每片地块上都没有树木。 你的目标是:在每片地块上均种植一棵树木,并使得 $i$ 号地块上的树的高度生长到不低于 $a_i$ 米。 你每天可以选择一个未种树且**与某个已种树的地块直接邻接**(**即通过单条道路相连**)的地块,种一棵高度为 $0$ 米的树。如果所有地块均已种过树,则你当天不进行任何操作。特别地,第 $1$ 天你只能在 $1$ 号空地种树。 对每个地块而言,从该地块被种下树的当天开始,该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同,在第 $x$ 天,$i$ 号地块上的树会长高 $\max(b_i + x \times c_i, 1)$ 米。注意这里的 $x$ 是从整个任务的第一天,而非种下这棵树的第一天开始计算。 你想知道:最少需要多少天能够完成你的任务?
输入
输入的第一行包含一个正整数 $n$,表示森林的地块数量。 接下来 $n$ 行:每行包含三个整数 $a_i, b_i, c_i$,分别描述一片地块,含义如题目描述中所述。 接下来 $n-1$ 行:每行包含两个正整数 $u_i, v_i$,表示一条连接地块 $u_i$ 和 $v_i$ 的道路。
输出
输出一行仅包含一个正整数,表示完成任务所需的最少天数。
样例输入输出
输入#1
复制
4 12 1 1 2 4 -1 10 3 0 7 10 -2 1 2 1 3 3 4
输出#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$ 米。 【数据范围】 对于所有测试数据有:$1 ≤ 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^9$ 天内完成任务。 ![T4](https://cdn.luogu.com.cn/upload/image_hosting/aqqd4l0y.png?x-oss-process=image/resize,m_lfit,h_400,w_300) 特殊性质 A:对于所有 $1 ≤ i ≤ n$,均有 $c_i = 0$; 特殊性质 B:对于所有 $1 ≤ i < n$,均有 $u_i = i$、$v_i = i + 1$; 特殊性质 C:与任何地块直接相连的道路均不超过 $2$ 条; 特殊性质 D:对于所有 $1 ≤ i < n$,均有 $u_i = 1$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
提高+/省选-
标签
点击显示
if ($pr_flag) { ?>
递交数
0
已通过
0
} ;?>
通过率
0%
时间限制
1 秒
内存限制
512 MB
来源
2023CSP-S
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和