Person in Charge

• SleepingCup

Problem Description

You are a forest caretaker. One day, you receive a task: plant trees on the plots of a forest and nurture them until they grow to specified heights.

The forest map consists of $n$ plots, with plot $1$ connected to the forest entrance. There are $n-1$ roads connecting these plots, ensuring that every plot is reachable from any other. Initially, no trees are planted on any plot.

Your goal is to plant one tree on each plot and ensure that the tree on the $i$-th plot grows to a height of at least $a_i$ meters.

Each day, you may choose an unplanted plot that is directly adjacent (i.e., connected by a single road) to a plot with an already planted tree and plant a tree of height $0$ meters. If all plots have been planted, you perform no operation that day. Specifically, on the first day, you can only plant a tree on plot $1$.

For each plot, starting from the day it is planted, the tree on that plot grows in height daily. Due to varying climate and soil conditions, on the $x$-th day, the tree on the $i$-th plot will grow by $\max(b_i + x \times c_i, 1)$ meters. Note that $x$ is counted from the first day of the entire task, not the day the tree was planted.

You want to know: what is the minimum number of days required to complete your task?

Input Format

The first line of input contains a positive integer $n$, the number of plots in the forest.

The next $n$ lines each contain three integers $a_i$, $b_i$, $c_i$, describing the $i$-th plot as explained in the problem description.

The following $n-1$ lines each contain two positive integers $u_i$, $v_i$, representing a road connecting plots $u_i$ and $v_i$.

Output Format

Output a single positive integer, the minimum number of days required to complete the task.

Samples

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

5

Sample 1 Explanation

Day $1$: Plant a tree on plot $1$. The tree on plot $1$ grows to $2$ meters.

Day $2$: Plant a tree on plot $3$. The trees on plots $1$ and $3$ grow to $5$ and $3$ meters, respectively.

Day $3$: Plant a tree on plot $4$. The trees on plots $1$, $3$, and $4$ grow to $9$, $6$, and $4$ meters, respectively.

Day $4$: Plant a tree on plot $2$. The trees on plots $1$, $2$, $3$, and $4$ grow to $14$, $1$, $9$, and $6$ meters, respectively.

Day $5$: The trees on plots $1$, $2$, $3$, and $4$ grow to $20$, $2$, $12$, and $7$ meters, respectively.

Sample 2

See the files tree/tree2.in and tree/tree2.ans in the contestant directory.

Sample 3

See the files tree/tree3.in and tree/tree3.ans in the contestant directory.

Sample 4

See the files tree/tree4.in and tree/tree4.ans in the contestant directory.

Data Range

For all test data: $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$. It is guaranteed that a solution exists within $10^9$ days.

Special Property A: For all $1 \le i \le n$, $c_i = 0$;

Special Property B: For all $1 \le i < n$, $u_i = i$ and $v_i = i + 1$;

Special Property C: No plot is directly connected to more than $2$ roads;

Special Property D: For all $1 \le i < n$, $u_i = 1$.