该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你是一名航标管理员，有一天，你接到了一个任务：在一片群岛的岛屿上修建灯塔，并养护至信号强度达到指定的数值。

群岛的航道图有 $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
15 2 1
9 5 -1
6 3 0
4 1 0
1 2
2 3
1 4

样例输出 #1

7

样例输入 #2

12
18 3 0
6 2 0
25 4 1
9 5 -1
7 1 0
11 2 1
5 6 -2
30 5 0
14 3 1
8 4 -1
21 6 0
10 1 0
1 2
2 3
3 4
4 5
2 6
6 7
1 8
8 9
9 10
10 11
11 12

样例输出 #2

17

样例输入 #3

5
30 1 0
14 6 -2
16 5 -1
6 1 1
22 10 -3
1 2
1 3
1 4
1 5

样例输出 #3

30

提示

【样例 1 解释】

第 $1$ 天：在岛屿 $1$ 修建灯塔，岛屿 $1$ 的灯塔信号强度增长至 $3$。

第 $2$ 天：在岛屿 $2$ 修建灯塔，岛屿 $1, 2$ 的灯塔信号强度分别增长至 $7, 3$。

第 $3$ 天：在岛屿 $4$ 修建灯塔，岛屿 $1, 2, 4$ 的灯塔信号强度分别增长至 $12, 5, 1$。

第 $4$ 天：在岛屿 $3$ 修建灯塔，岛屿 $1, 2, 3, 4$ 的灯塔信号强度分别增长至 $18, 6, 3, 2$。

第 $5$ 天：岛屿 $1, 2, 3, 4$ 的灯塔信号强度分别增长至 $25, 7, 6, 3$。

第 $6$ 天：岛屿 $1, 2, 3, 4$ 的灯塔信号强度分别增长至 $33, 8, 9, 4$。

第 $7$ 天：岛屿 $1, 2, 3, 4$ 的灯塔信号强度分别增长至 $42, 9, 12, 5$。此时四座灯塔的信号强度分别不低于 $15, 9, 6, 4$，任务完成。

【数据范围】

对于所有测试数据有：$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$。