Highway Cost Calculation

C country has a network of highways forming a tree. There are \(n\) cities numbered from 1 to \(n\), connected by \(n-1\) highways. City 1 is the capital and is used as the root of the tree. For each other city \(i\) (\(2\le i\le n\)) there is a local bus company that can take a passenger from city \(i\) to any other city \(j\) at a cost of \(P_i \times D + Q_i\), where \(D\) is the distance (i.e. the number of edges in the simple path between \(i\) and \(j\)) and \(P_i, Q_i\) are given integers. Moreover, it is guaranteed that if city \(i\) is an ancestor of city \(j\) in the tree (that is, on the unique simple path from \(j\) to the capital), then \(P_i \le P_j\).

For each city (except the capital), determine the minimum cost for a person starting at that city to reach the capital (city 1). A passenger can take one or more bus rides; formally, if a passenger is in city \(i\) (with \(i\ge 2\)), they can choose an ancestor \(v\) (which may be the capital) and pay a cost of \[ P_i \times (\text{depth}(i) - \text{depth}(v)) + Q_i\] plus the cost to move from \(v\) to the capital (which is 0 if \(v\) is the capital). The depth of a city is its distance from the capital (with \(\text{depth}(1)=0\)).

Your task is to compute this minimum cost for every city from 2 to \(n\).

inputFormat

The input is given as follows:

1. The first line contains a single integer \(n\) (\(2 \le n \le 10^5\)) denoting the number of cities.
2. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le n\)) representing a highway connecting cities \(u\) and \(v\). It is guaranteed that these highways form a tree with city 1 as the root.
3. The next line contains \(n-1\) integers: \(P_2, P_3, \dots, P_n\), where \(P_i\) is the coefficient for city \(i\)'s bus company.
4. The next line contains \(n-1\) integers: \(Q_2, Q_3, \dots, Q_n\), where \(Q_i\) is the fixed fee for city \(i\)'s bus company.

outputFormat

Output \(n-1\) lines. The \(i\)th line (for \(2 \le i \le n\)) should contain a single integer representing the minimum cost to travel from city \(i\) to the capital (city 1).

sample

3
1 2
1 3
3 5
10 2

13
7