25662번 - Flower's Land 다국어

The Kingdom of Flowers consists of $n$ cities, and the $i$-th city grows $a_i$ flowers. There are $n-1$ roads, where the $i$-th road connects cities $u_i$ and $v_i$. It is guaranteed that for any two cities there is a path connecting them.

Now, the Kingdom of Flowers wants to hold a flower exhibition. To do that, you need to first choose a city $z$ to build an exhibition hall, and then select exactly $k$ cities $x_1, x_2, \ldots, x_k$ and transport the flowers from those $k$ cities to the city $z$.

To avoid upsetting people in cities along the path, the organizers stipulated that if city $x$ was selected, then all cities on the path from $x$ to $z$ had to be selected as well. In particular, this means that city $z$ must be selected.

For each $z = 1, 2, \ldots, n$, find the maximum number of flowers that can be transported if city $z$ is chosen to build the exhibition hall.

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 40\,000$, $1 \le k \le \min(n, 3000)$).

The next line of the input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 5 \cdot 10^5$).

Each of the next $n-1$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$), indicating that there is an edge between vertices $x$ and $y$. It is guaranteed that the given graph is a tree.

Output a single line containing $n$ integers $f_1, f_2, \ldots, f_n$, where $f_i$ denotes the answer for $z = i$.