### Component

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

#### Problem Description

Given a tree with weight assigned to nodes, find out minimum total weight connected component with fixed number of node.

#### Input

The first line contains a single integer $$n$$.

The second line contains $$n$$ integers $$w_1, w_2, \ldots, w_n$$. $$w_i$$ denotes the weight of the node $$i$$.

The following $$(n - 1)$$ lines with two integers $$a_i$$ and $$b_i$$, which denote the edge between $$a_i$$ and $$b_i$$.

Note that the nodes are labled by $$1, 2, \ldots, n$$.

($$1 \leq n \leq 2 \cdot 10^3, 1 \leq w_i \leq 10^5$$)

#### Output

$$n$$ integers $$c_1, c_2, \ldots, c_n$$. $$c_i$$ stands for the minimum total weight component with $$i$$ nodes.

#### Sample Input

3
1 2 3
1 2
2 3 

#### Sample Output

1 3 6


ftiasch

#### Manager

Information
 Solved Number 53 Submit Number 237
Problem Tags
dp
trees
No tag edit access