当前没有测试数据。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

森林有 $n$ 片地块和 $n-1$ 条连接地块的道路，任意两片地块之间均能相互到达，$1$ 号地块连接入口。最开始所有地块都没有树。

你需要在每片地块种一棵树，并使第 $i$ 片地块的树高最终不低于 $a_i$ 米。每天选择一个尚未种树、且与某个已种树地块直接相邻的地块，种一棵高度为 $0$ 米的树。特别地，第 $1$ 天只能在 $1$ 号地块种树。所有地块都已种树后，当天不再进行种植操作。

从种下的当天起，第 $i$ 片地块上的树在任务第 $x$ 天会长高 $\max(b_i+x c_i,1)$ 米。这里的 $x$ 从整个任务的第一天开始计算，并不是从该树种下的第一天开始计算。

求完成任务所需的最少天数。

输入格式

第一行一个正整数 $n$。接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$，描述第 $i$ 片地块。随后 $n-1$ 行，每行两个正整数 $u_i,v_i$，表示一条道路连接的地块。

输出格式

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

样例 1

输入

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

输出

5

数据范围

$1\le n\le10^5$，$1\le a_i\le10^{18}$，$1\le b_i\le10^9$，$|c_i|\le10^9$，$1\le u_i,v_i\le n$。保证存在方案能在 $10^9$ 天内完成任务。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF