Forest Tree Planting and Growth

You are a forest caretaker given a task to plant and nurture trees in a forest represented by n plots. The forest is laid out as follows:

• There are n plots numbered 1 through n. Plot 1 is connected to the forest entrance.
• There are n-1 roads; each road connects two plots, and the entire set of plots is connected (i.e. the graph is a tree).
• Initially no plot has a tree planted on it.

Your objective is to plant one tree on every plot such that, for each plot i, the tree eventually reaches a height of at least a_i meters.

The rules of planting and growth are as follows:

1. Planting rules:
   • On day 1, you must plant a tree (of height 0) on plot 1.
   • On every subsequent day, you may choose one plot that has not yet had a tree planted and is adjacent (directly connected by a single road) to some plot where a tree has already been planted, and plant a tree (of height 0) there. If every plot has already been planted with a tree, you do nothing on that day.
2. Growth rules:

   For each plot, starting from the day it is planted, its tree grows every day. On the x-th day of the overall task, the tree in plot i grows by an amount equal to

   \( \max(b_i + x \times c_i,\; 1) \) meters,

   where the parameters b_i and c_i may differ between plots. Note that x is the global day count (starting at 1), not the number of days since the tree at plot i was planted.

Because of the planting restriction, the earliest possible day a tree can be planted on plot i is dist[i] + 1, where dist[i] is the distance (in number of roads) from plot 1. In other words, in an optimal strategy, tree i is planted on day \(p_i = dist[i] + 1\).

Your task is to determine the minimum number of days needed to complete the task (i.e. plant trees on every plot such that the height requirement is met on every plot by the end of that day).

Note on height calculation: For a tree planted on day p and matured by day T, its height is

\( H = \sum_{x=p}^{T} \max(b_i + c_i \times x,\; 1) \).

inputFormat

The first line contains an integer n (number of plots).

The second line contains n integers \(a_1, a_2, \ldots, a_n\) where \(a_i\) is the minimum required height (in meters) for the tree at plot i.

The third line contains n integers \(b_1, b_2, \ldots, b_n\).

The fourth line contains n integers \(c_1, c_2, \ldots, c_n\).

Each of the next n-1 lines contains two integers \(u\) and \(v\), indicating that there is a road connecting plot \(u\) and plot \(v\).

outputFormat

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

sample

3
10 5 6
1 0 1
1 1 2
1 2
2 3

4