King Byteur's Dream: Minimizing Total Threat

King Byteur of Byteotia has a dream of conquering Bitotia. In his dream, Bitotia is represented as a tree with n cities (numbered from 1 to n) and n-1 bidirectional roads connecting them such that there is a unique simple path between any two cities. However, the exact network is random in his mind.

The king plans to split Bitotia into k states by secretly destroying exactly k-1 roads. When a road is removed, the tree splits into two connected components (states). Each city i has a military coefficient a_i. If a state has a total military coefficient sum S (i.e. the sum of a_i over all cities in that state), its threat level is defined as \(S^2\) in LaTeX. The total threat is the sum of the threat levels of all states.

Your task is to compute, for every k from 1 to n, the minimal possible total threat achievable by choosing exactly k-1 roads to remove. Note that when k = 1, no roads are removed.

Hint: Observe that with no cuts, the threat is \(T^2\) where \(T=\sum_{i=1}^{n}a_i\). Removing an edge that splits the tree into components with sums \(S\) and \(T-S\) changes the threat to \(S^2+(T-S)^2 = T^2-2S(T-S)\). Thus, each removed edge gives a reduction of \(2S(T-S)\). The optimal solution for each k can be found by selecting the best k-1 cuts in terms of this reduction.

inputFormat

The first line contains an integer n (number of cities).

The second line contains n space-separated integers: a₁, a₂, …, a_n, where a_i is the military coefficient of city i.

Each of the next n-1 lines contains two space-separated integers u and v (1 ≤ u,v ≤ n), representing a road connecting city u and city v.

outputFormat

Output n space-separated integers. The k^th integer should be the minimal total threat achieved by splitting the tree into k states.

sample

4
1 2 3 4
1 2
2 3
3 4

100 68 50 30