Connecting Forests After Vertex Removal

You are given a tree with \(n\) vertices. Each vertex \(i\) has an integer weight \(w_i\). For each vertex \(u\) \( (1 \le u \le n)\), consider the following procedure:

• Remove vertex \(u\) and all edges incident to it. This splits the tree into a forest (i.e. several connected components).
• To make the remaining graph connected, you are allowed to perform the following operation any number of times (possibly zero) in any order:

1. Choose two (not necessarily distinct) vertices \(x\) and \(y\) that are in different connected components.
2. Pay \(w_x + w_y\) coins, then add an edge between \(x\) and \(y\).
3. After adding the edge, update the weights of the chosen vertices by decreasing each by \(1\) (i.e. if the current weight is \(w_x\), it will be replaced by \(w_x - 1\); similarly for \(w_y\)).

Your task is to compute the minimum number of coins required to connect the forest for each possible vertex \(u\) that is removed. If the forest is already connected (or empty), the cost is \(0\).

Observation: Suppose after removing a vertex, the forest is divided into \(k\) connected components. In each component let \(m_i\) be the minimum weight of any vertex in that component. Then an optimal strategy is to choose the component having the smallest \(m_i\) (say \(g\)) as a hub and connect every other component to it. Note that if the hub is used more than once then its cost for each subsequent connection decreases by \(1\) each time. In fact, the total minimum cost to connect \(k\) components is given by:

[ \text{cost} = \begin{cases} 0, & \text{if } k \le 1;\ \sum_{i\neq i_0} m_i + (k-1),g - \frac{(k-1)(k-2)}{2}, & \text{if } k\ge2, \end{cases} ]

where \(g = \min_{1 \le i \le k} m_i\) and \(i_0\) is an index of a component with \(m_{i_0} = g\).

inputFormat

The input consists of:

1. A line containing an integer \(n\) \((1 \le n \le 2000)\), the number of vertices in the tree.
2. A line containing \(n\) integers \(w_1, w_2, \dots, w_n\) \((1 \le w_i \le 10^9)\) representing the weight of each vertex.
3. \(n-1\) lines, each containing two integers \(u\) and \(v\) \((1 \le u, v \le n)\) representing an undirected edge between vertices \(u\) and \(v\).

It is guaranteed that the given edges form a tree.

outputFormat

Output \(n\) lines. The \(i\)-th line should contain a single integer: the minimum number of coins required to reconnect the forest after vertex \(i\) is removed.

sample

4
4 3 2 5
1 2
1 3
1 4

11
0
0
0