#770. [CSP-S2023 D] 种树

[CSP-S2023 D] 种树

题目描述

你是一个森林养护员,有一天,你接到了一个任务:在一片森林内的地块上种树,并养护至树木长到指定的高度。

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

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

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

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

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

输入格式

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

接下来 nn 行:每行包含三个整数 ai,bi,cia_i, b_i, c_i,分别描述一片地块,含义如题目描述中所述。

接下来 n1n-1 行:每行包含两个正整数 ui,viu_i, v_i,表示一条连接地块 uiu_iviv_i 的道路。

输出格式

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

4
12 1 1
2 4 -1
10 3 0
7 10 -2
1 2
1 3
3 4
5

输入/输出数据 2

见选手目录下的 tree2.intree2.ans

输入/输出数据 3

见选手目录下的 tree3.intree3.ans

输入/输出数据 4

见选手目录下的 tree4.intree4.ans

样例 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 米。

数据范围

对于所有测试数据有:$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$。保证存在方案能在 10910^9 天内完成任务。

测试点编号 nn\le 特殊性质
11 2020 A\text A
242\sim4
565\sim6 500500 A\text A
787\sim8 10510^5
9109\sim10 B\text B
111311\sim13 C\text C
141614\sim16 D\text D
172017\sim20
  • 特殊性质 A:对于所有 1in1 ≤ i ≤ n,均有 ci=0c_i = 0
  • 特殊性质 B:对于所有 1i<n1 ≤ i < n,均有 ui=iu_i = ivi=i+1v_i = i + 1
  • 特殊性质 C:与任何地块直接相连的道路均不超过 22 条;
  • 特殊性质 D:对于所有 1i<n1 ≤ i < n,均有 ui=1u_i = 1