#CSPS2023D. 种树(tree)
种树(tree)
题目描述
你是一个森林养护员,有一天,你接到了一个任务:在一片森林内的地块上种树,并养护至树木长到指定的高度。
森林的地图有 片地块,其中 号地块连接森林的入口。共有 条道路连接这些地块,使得每片地块都能通过道路互相到达。最开始,每片地块上都没有树木。
你的目标是:在每片地块上均种植一棵树木,并使得 号地块上的树的高度生长到不低于 米。
你每天可以选择一个未种树且与某个已种树的地块直接邻接(即通过单条道路相连)的地块,种一棵高度为 米的树。如果所有地块均已种过树,则你当天不进行任何操作。特别地,第 天你只能在 号空地种树。
对每个地块而言,从该地块被种下树的当天开始,该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同,在第 天, 号地块上的树会长高 米。注意这里的 是从整个任务的第一天,而非种下这棵树的第一天开始计算。
你想知道:最少需要多少天能够完成你的任务?
输入格式
输入的第一行包含一个正整数 ,表示森林的地块数量。
接下来 行:每行包含三个整数 ,分别描述一片地块,含义如题目描述中所述。
接下来 行:每行包含两个正整数 ,表示一条连接地块 和 的道路。
输出格式
输出一行仅包含一个正整数,表示完成任务所需的最少天数。
4
12 1 1
2 4 -1
10 3 0
7 10 -2
1 2
1 3
3 4
5
提示
【样例 1 解释】
第 天:在地块 种树,地块 的树木长高至 米。
第 天:在地块 种树,地块 的树木分别长高至 米。
第 天:在地块 种树,地块 的树木分别长高至 米。
第 天:在地块 种树,地块 的树木分别长高至 米。
第 天:地块 的树木分别长高至 米。
【样例 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 ≤ n$。保证存在方案能在 天内完成任务。
特殊性质 A:对于所有 ,均有 ;
特殊性质 B:对于所有 ,均有 、;
特殊性质 C:与任何地块直接相连的道路均不超过 条;
特殊性质 D:对于所有 ,均有 。