시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 2048 MB111100.000%

## 문제

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$.

## 예제 입력 1

5 3
6 10 4 3 4
3 4
4 2
2 5
5 1


## 예제 출력 1

20 20 17 17 20


## 예제 입력 2

7 4
1 3 2 1 7 12 17
4 6
1 4
5 1
2 5
7 6
3 2


## 예제 출력 2

31 13 13 31 21 31 31