Chess Moves on Tree

Chess is like life: every move is irreversible and must be weighed carefully. In this problem, you are given a tree with n nodes. The i-th node initially holds b_i chess pieces and can hold at most a_i pieces. For a designated root k, you are allowed to perform the following operation repeatedly: choose a node (other than k) that currently has at least one chess piece, and move one chess piece from that node to its parent – but only if after adding this piece the parent's total number of pieces does not exceed its limit. Formally, if a node u has parent p in the tree rooted at k, you can move a piece from u to p provided that the number of pieces at p is less than a_p.

Your goal is to minimize the sum of distances from every chess piece to the root k after performing a sequence of moves. Initially, every chess piece located at node i contributes a distance of dist(i,k) (i.e. the number of edges on the unique path from i to k). Each valid move decreases the total distance by 1. For every possible choice of the root, i.e. for k = 1, 2, …, n, compute the minimum possible sum of distances that can be achieved.

It can be shown that the maximum number of moves you can make when the tree is rooted at k is given by summing up, over every non-root node u,

$$f(u) = \min\Bigl(b_u + \sum_{v \in \text{child}(u)} f(v),\; a_u - b_u\Bigr). $$

If we denote the initial total distance as

$$D = \sum_{i=1}^{n} {\rm depth}(i,k) \times b_i,$$

then the answer for root k is

$$D - \sum_{u \neq k} f(u).$$

Note: The tree is given as an undirected acyclic graph. For each choice of root k, you must re-root the tree accordingly, which may change parent-child relationships.

Good luck, and remember: every move counts!

inputFormat

The input begins with an integer n (the number of nodes in the tree). The next line contains n integers b₁, b₂, …, b_n, where b_i is the initial number of chess pieces at node i. The following line contains n integers a₁, a₂, …, a_n, where a_i is the maximum number of pieces that can be held at node i (assume that b_i ≤ a_i for all i). Each of the next n - 1 lines contains two integers u and v indicating that there is an edge connecting node u and node v (the tree is undirected).

You must compute the answer for every possible root k = 1, 2, …, n.

outputFormat

Output n integers separated by spaces, where the k-th integer is the minimum total distance sum achievable when the tree is rooted at node k.

sample

3
1 1 1
2 2 2
1 2
2 3

1 0 1