Description

LQ Company is a world-famous oil company that supplies high-quality oil to the world.

Recently, LQ Company discovered a large oilfield area in a forest, where $n$ oil wells can be developed.

LQ Company built $n-1$ roads among these $n$ wells. Each road connects two wells, does not pass through any other well along the way, and these roads connect all wells.

Building a well requires a large piece of equipment, which is very hard to transport. LQ Company plans to build an air station at one of the wells: first airlift the equipment to the air station, then transport this equipment along the roads they built to construct different wells. After all wells are constructed, the equipment is moved out from the air station.

To reduce transportation trouble, the company requires the total distance traveled by the equipment on the roads to be as short as possible.

During the construction and extraction process, some manpower is needed. The $i$-th well requires $B_i$ workers for construction, and once the well is completed, it requires $S_i$ workers to stay at the well for maintenance.

Of course, if a person participates in constructing a well, they can directly stay to maintain that well, or participate in constructing the next well. However, workers who are maintaining wells cannot participate in the construction of subsequent wells.

Now LQ Company wants to know: what is the minimum possible total path length for transporting the equipment? Under the condition that the total path length is minimized, what is the minimum manpower needed to complete the construction and maintenance of all wells?

Input Format

The first line contains an integer $n$, the number of oil wells. The wells are numbered from $1$ to $n$.

The second line contains $n$ integers, representing $B_1,B_2,\cdots,B_n$, separated by single spaces.

The third line contains $n$ integers, representing $S_1,S_2,\cdots,S_n$, separated by single spaces.

The next $n-1$ lines describe the roads between wells. The $i$-th of these lines contains two integers $a$, $b$, separated by a single space, meaning that there is a road whose start is $i+1$, whose end is $a$, and whose length is $b$. The road is bidirectional: the equipment can be transported from either end to the other. Each road can be used any number of times. The testdata guarantees that any two wells can be connected via the roads.

Output Format

Output two integers separated by a single space: the minimum total distance that the equipment needs to be transported in the optimal plan, and the minimum manpower required under the condition that the total distance is minimized.

6
3 10 20 7 15 9
2 6 10 4 8 7
1 9
1 2
2 5
3 4
3 7

54 38

2
10 20
15 15
1 8

16 30

Hint

[Sample Explanation 2]

There are two plans that achieve the optimum.

Plan 1: Build the air station at well $2$. First build well $2$, then transport the equipment to well $1$ to build well $1$, and finally transport the equipment back to well $2$.

Plan 2: Build the air station at well $1$. First transport the equipment to well $2$ to build well $2$, then transport the equipment to well $1$.

[Constraints]

For $20\%$ of the data: $n$ does not exceed $10$.

For another $20\%$ of the data: each well has roads directly connecting it to at most two other wells.

For another $10\%$ of the data: there are $n-1$ wells that have only one road connecting them to other wells.

For $100\%$ of the data: $1 \le n \le 10^5$, and $B$, $S$, and $c$ are all positive integers not exceeding $10000$.

Time limit: 1 second, 256 MB. Lanqiao Cup 2018, the 9th National Contest.

Translated by ChatGPT 5