题目描述

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

森林的地图有$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$的道路。

输出格式

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

输入输出样例

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

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$天内完成任务。

特殊性质 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$。