The Tree of Haruhi Suzumiya

The members in *SOS Dan(**S**ekai o **O**oini Moriageru Tame no **S**uzumiya Haruhi no Dan)* want to assemble a Christmas tree(you know many Christmas trees are decorations not real trees).

The tree contains $n$ vertices which are numbered from $1$ to $n$. The weight of vertex $i$ is $w_i$. The number of edges on the path from vertex $i$ to vertex $1$(vertex $1$ is important because it's the top one) is denoted as $d_i$.

Haruhi says, "I don't like the vertex pairs $(i,j)$ that $i$ is the ancestor of $j$ and $w_i > w_j$ ".

Kyon says, "I don't like the vertex pairs $(i,j)$ that $i$ is the ancestor of $j$ and $w_i < w_j$".

Itsuki says, "I don't like the vertex pairs $(i,j)$ that $i<j$ and neither $i$ nor $j$ is the ancestor of the other one".

Mikuru says, "I don't like the vertices that are far away from vertex $1$".

Yuki says nothing.

Now they are divided into two groups to assemble the tree. Haruhi and Itsuki are in group $A$ while Kyon and Mikuru are in group $B$. Both group choose some vertices to assemble. Each vertex should be chosen by exactly $1$ group.

Let's denote the vertices set group $A$ chose as $V(A)$, the vertices set group $B$ chose as $V(B)$. The dislike level of group $A$ is $$|\lbrace vertex \; pair \; (i,j) \; that \; is \; disliked \; by \; either \; Haruhi \; or \; Itsuku | i \in V(A) \bigwedge j \in V(A) \rbrace|$$. The dislike level of group $B$ is $$|\lbrace vertex \; pair \; (i,j) \; that \; is \; disliked \; by \; Kyon| i \in V(B) \bigwedge j \in V(B) \rbrace|+\sum_{u \in V(B)} d_u$$.

Yuki wants to know the minimum value of the sum of dislike level of group $A$ and $B$ when $|V(B)|=1,2,3,\cdots,n$ respectively.

The first line contains an integer $n(1\le n \le 10^6)$ denoting the number of vertices on the tree.

The second line contains $n$ integer $w_i(1 \le w_i \le 10^6)$ denoting the weight of vertex $i$.

Next $n-1$ lines each contains two integer $u,v(1\le u,v \le n)$, denoting there is an edge between $u$ and $v$.

Output $n$ lines. The $i-th$ of them contains an integer denoting the answer when $|V(B)|=i$.

4
4 1 2 3
1 2
2 3
2 4

9
5
2
1
2

642ccpcQHD