Flower's Land

The Kingdom of Flowers has $n$ cities, and city $i$ grows $a_i$ flowers. There are $n-1$ roads, and the $i$-th road connects cities $u_i$ and $v_i$. Any two cities are connected by a path.

The kingdom wants to hold a flower exhibition. First, choose a city $z$ to build the exhibition hall. Then select exactly $k$ cities $x_1, x_2, \ldots, x_k$ and transport their flowers to city $z$.

The organizers require that if city $x$ is selected, then every city on the path from $x$ to $z$ must also be selected. In particular, city $z$ must be selected.

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

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

The second line 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$), meaning there is an edge between vertices $x$ and $y$. The given graph is guaranteed to be a tree.

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