The Tree of Haruhi Suzumiya
Time Limit: 8000/6000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 2 Accepted Submission(s): 1
Problem Description
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 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.
Input
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$.
样例解释
$B=\emptyset,\lbrace 3 \rbrace, \lbrace 3,4 \rbrace, \lbrace 1,3,4 \rbrace,\lbrace 1,2,3,4 \rbrace$ respectively.
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$.
Hint
样例解释
$B=\emptyset,\lbrace 3 \rbrace, \lbrace 3,4 \rbrace, \lbrace 1,3,4 \rbrace,\lbrace 1,2,3,4 \rbrace$ respectively.
Output
Output $n$ lines. The $i-th$ of them contains an integer denoting the answer when $|V(B)|=i$.
Sample Input
4 4 1 2 3 1 2 2 3 2 4
Sample Output
9 5 2 1 2
Source
642ccpcQHD