Optimal Oil Well Establishment

LQ Corporation, a leading oil company, has discovered a large oil field in a forest. In this field, there are n oil wells and n-1 roads connecting them in a tree structure (each road connects two wells, and no road passes through any other well). The company plans to establish an air station at one of the oil wells. The heavy equipment needed to build a well is first airlifted to the air station and then transported along the roads to build the other wells one by one. After all wells are built, the equipment is airlifted away from the station.

In order to minimize the hassle, LQ Corporation requires that the total distance traveled by the heavy equipment along the roads is minimized. Assume each road has a unit length. In other words, if the air station is chosen as node u, the transportation distance is

\( T = \sum_{v=1}^{n} \text{dist}(u,v) \)

and the company will choose the node u that minimizes \( T \).

---

In addition, constructing each oil well involves manpower. For the i-th well:

• It requires \( B_i \) people to participate in its construction.
• Once built, the well needs \( S_i \) people to remain on-site permanently for maintenance.

A person who works on constructing a well can either remain to maintain that well or join the construction of a subsequent well; however, anyone assigned to maintenance cannot participate in any later construction. The company can choose the order in which to construct the wells. Under an optimal ordering, if at the moment of constructing a well the number of available (free) people is f, then the construction of a well with parameters \( (B_i, S_i) \) requires that \( f \ge B_i \), and after the well is constructed, exactly \( S_i \) people stay permanently (thus, the free manpower reduces by \( S_i \)).

The goal is to determine:

1. The minimal total transportation distance \( T_{min} \) when the air station is chosen optimally.
2. Under that optimal transportation plan, the minimum initial number of personnel required such that, by choosing an appropriate construction order, every well can be built and maintained.

Hint: For the manpower part, note that if you order the wells in a sequence \( (i_1, i_2, \ldots, i_n) \), and let the free manpower before building well \( i_k \) be \( f_k \), then the condition must satisfy:

\( f_k \ge B_{i_k} \)

with \( f_1 = X \) (the initial manpower) and \( f_{k+1} = f_k - S_{i_k} \). Thus, an optimal ordering minimizes the maximum value of \( \text{(cumulative maintenance cost before a task)} + B_i \). A greedy strategy is to sort wells in descending order of \( (B_i - S_i) \).

inputFormat

The input is given as follows:

1. The first line contains a single integer \( n \) denoting the number of oil wells.
2. Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \) indicating there is a road connecting well \( u \) and well \( v \).
3. The next line contains \( n \) integers: \( B_1, B_2, \ldots, B_n \), where \( B_i \) is the number of people required for construction of the i-th well.
4. The last line contains \( n \) integers: \( S_1, S_2, \ldots, S_n \), where \( S_i \) is the number of people that must remain for maintenance at the i-th well.

All numbers are separated by spaces.

outputFormat

Output two integers separated by a space:

• The first integer is the minimal total transportation distance \( T_{min} \) when the air station is chosen optimally.
• The second integer is the minimum number of personnel required to complete the construction and maintenance of all oil wells under an optimal construction order.

sample

1
5
3

0 5