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 

Source

ftiasch

Manager

Information
Solved Number53
Submit Number237
Problem Tags
dp
trees
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel