Minimizing Weighted Cost in a Rooted Tree Assimilation Process

You are given a rooted tree T with n nodes. The tree is defined as follows: there is a distinguished root node (node 1) and every other node has a unique parent. Each node i carries two positive integer weights, a_i and b_i. For any subtree T' of T (a connected subgraph of T that is itself a rooted tree with some node as its root), define its ratio as

\(r(T') = \frac{a(T')}{b(T')}\) , where \(a(T') = \sum_{j \in T'} a_j\) and \(b(T') = \sum_{j \in T'} b_j\).

For every node i let \(F_i\) denote the family of all subtrees of T rooted at i. Then define a special subtree T_i as the one satisfying:

• \(r(T_i) = \min_{T' \in F_i} r(T')\), and
• among all subtrees achieving this minimal ratio, T_i is chosen to have the maximum number of nodes.

Next, for any subtree T' of T, define its sibling set as follows: for any node j (with parent i), we have \(j \in S(T')\) if and only if i is in T' but j is not.

The assimilation process on the tree is performed as follows. Initially, set a working set \(Q \leftarrow \{1\}\) (the root node). Then, while \(Q \neq \emptyset\), do:

1. Choose an arbitrary node \(j \in Q\).
2. Determine the subtree \(T_j\) (i.e. the optimal subtree rooted at j as defined above) based on the current values of a and b.
3. For every node k in \(S(T_j)\) (all children of j that were not included in \(T_j\)), update a_k as follows: \[ a_k \leftarrow a_k + \lceil r(T_j) \rceil, \] where \(\lceil x \rceil\) is the smallest integer not less than \(x\>.
4. Remove \(j\) from \(Q\) and add all nodes in \(S(T_j)\) to \(Q\).

Assume that during the process the step (2) is executed exactly \(m\) times, and let \(K_i\) be the subtree determined during the \(i\)th execution. The cost W is defined as:

\(W = \sum_{i=1}^{m} i \times \lceil r(K_i) \rceil\).

Your task is to choose the order in which nodes from \(Q\) are processed (i.e. you decide the order of activations) so that all nodes eventually are assimilated and the total cost W is minimized. In other words, you must compute the minimum possible value of W achievable by an optimal processing order.

Note: In the definition of the optimal subtree T_i for a node i, the choice is made by examining all subtrees rooted at i. One may show that the following recursive strategy works in determining \(T_i\):

• Let the base of i be the pair \((a_i, b_i)\).
• For each child, compute its best (optimal) subtree value \((A_{child}, B_{child})\) with ratio \(r_{child} = \frac{A_{child}}{B_{child}}\).
• Then, by processing the children in increasing order of \(r_{child}\), include a child in the subtree of i if doing so does not increase the current ratio, i.e. if \[ \frac{a_i + A_{child}}{b_i + B_{child}} \le \frac{a_i}{b_i}. \]

This recursion naturally extends to the simulation of the assimilation process. Use the updated values of a when a node is processed.

All formulas above are given in \(\LaTeX\) format.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nodes in the tree.

The next n lines each contain two positive integers a_i and b_i (1 ≤ a_i, b_i ≤ 10⁹), representing the initial weights of node i.

The following n-1 lines each contain two integers u and v (1 ≤ u,v ≤ n), indicating that node u is the parent of node v. It is guaranteed that the given graph is a rooted tree with node 1 as the root.

outputFormat

Output a single integer — the minimum possible total cost W achievable.

sample

1
3 2

2