[CSP-S 2023] 种树

题目描述

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

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

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

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

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

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

输入格式

输入的第一行包含一个正整数 \(n\)，表示森林的地块数量。

接下来 \(n\) 行：每行包含三个整数 \(a_i, b_i, c_i\)，分别描述一片地块，含义如题目描述中所述。

接下来 \(n-1\) 行：每行包含两个正整数 \(u_i, v_i\)，表示一条连接地块 \(u_i\) 和 \(v_i\) 的道路。

输出格式

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

样例 #1

样例输入 #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\) 米。

【样例 2】

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。

【样例 3】

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

【样例 4】

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

【数据范围】

对于所有测试数据有：\(1 \le n \le 10^5,1 \le a_i \le 10^{18}, 1 \le b_i \le 10^9,0 \le |c_i| \le 10^9, 1 \le u_i, v_i \le n\)。保证存在方案能在 \(10^9\) 天内完成任务。

特殊性质 A：对于所有 \(1 \le i \le n\)，均有 \(c_i = 0\)；

特殊性质 B：对于所有 \(1 \le i < n\)，均有 \(u_i = i\)、\(v_i = i + 1\)；

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

特殊性质 D：对于所有 \(1 \le i < n\)，均有 \(u_i = 1\)。