有一棵包含 $n$ 个节点的树，根为 $1$。第 $1$ 天在根节点种下一棵初始高度为 $0$ 的树；此后每天必须选择一个尚未种植、且与已种植节点相邻的节点种树，直到所有节点都已种植。

节点 $i$ 从种植当天开始，在每个全局日历日 $x$ 增加高度

$$\max(b_i+x\cdot c_i,1).$$

这里的 $x$ 是任务开始后的日期，而不是该树的树龄。求所有节点的高度均达到各自目标 $a_i$ 所需的最少天数。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行包含 $a_i,b_i,c_i$。最后给出 $n-1$ 行无向边 $u_i,v_i$。

输出格式

输出一个整数，表示最少需要的天数。保证存在不超过 $10^9$ 天的可行方案。

样例 1

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

5

数据范围与原题特殊限制

对于所有测试数据，保证：

• $1 \leq n \leq 10^5$；
• $1 \leq a_i \leq 10^{18}$，$1 \leq b_i \leq 10^9$，$0 \leq |c_i| \leq 10^9$；
• $1 \leq u_i,v_i \leq n$。

保证存在方案能在 $10^9$ 天内完成任务。

测试点编号	$n \leq$	特殊性质
$1$	$20$	$\text{A}$
$2\sim4$		无
$5\sim6$	$500$	$\text{A}$
$7\sim8$	$10^5$
$9\sim10$		$\text{B}$
$11\sim13$		$\text{C}$
$14\sim16$		$\text{D}$
$17\sim20$		无

特殊性质 $\text{A}$：对于所有 $1 \leq i \leq n$，均有 $c_i = 0$；

特殊性质 $\text{B}$：对于所有 $1 \leq i < n$，均有 $u_i = i,v_i = i + 1$；

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

特殊性质 $\text{D}$：对于所有 $1 \leq i < n$，均有 $u_i = 1$。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。