Problem Description

You are a forest caretaker. One day, you received a task: plant trees on the plots in a forest and take care of them until the trees grow to the required height.

The forest map has $n$ plots, and plot $1$ is connected to the forest entrance. There are $n - 1$ roads connecting these plots, so that any plot can reach any other plot through the roads. Initially, there are no trees on any plot.

Your goal is to plant one tree on every plot, and make the height of the tree on plot $i$ grow to at least $a_i$ meters.

Each day, you may choose one plot that has not been planted yet and is directly adjacent to some already planted plot (i.e. connected by a single road), and plant a tree of height $0$ meters there. If all plots have already been planted, then you do nothing that day. In particular, on day $1$, you can only plant a tree on the empty plot $1$.

For each plot, starting from the day when a tree is planted on that plot, the tree on that plot grows by a certain height every day. Due to different climate and soil conditions, on day $x$, the tree on plot $i$ grows by $\max(b_i + x \times c_i, 1)$ meters. Note that $x$ is counted from day $1$ of the entire task, not from the first day when this tree was planted.

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

Input Format

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

The next $n$ lines each contain three integers $a_i, b_i, c_i$, describing a plot, with meanings as stated in the description.

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

Output Format

Output a single line containing one positive integer, indicating the minimum number of days required to finish the task.

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

5

Hint

[Sample 1 Explanation]

Day $1$: Plant a tree on plot $1$, and the tree on plot $1$ grows to $2$ meters.

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

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

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

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

[Sample 2]

See tree/tree2.in and tree/tree2.ans in the contestants' directory.

[Sample 3]

See tree/tree3.in and tree/tree3.ans in the contestants' directory.

[Sample 4]

See tree/tree4.in and tree/tree4.ans in the contestants' directory.

[Constraints]

For all testdata: $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 there exists a plan that can finish the task within $10^9$ days.

::cute-table{tuack}

Special property $\text A$: for all $1 \le i \le n$, $c_i = 0$.

Special property $\text B$: for all $1 \le i < n$, $u_i = i, v_i = i + 1$.

Special property $\text C$: each plot is connected by at most $2$ roads to other plots.

Special property $\text D$: for all $1 \le i < n$, $u_i = 1$.

Translated by ChatGPT 5