问题 D: [CSP-S 2023] 种树

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

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

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

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

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

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

【数据范围】

对于所有测试数据有：$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$ 天内完成任务。

输入的第一行包含一个正整数 $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