|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|8 초 (추가 시간 없음)||2048 MB||1||1||1||100.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$.
5 3 6 10 4 3 4 3 4 4 2 2 5 5 1
20 20 17 17 20
7 4 1 3 2 1 7 12 17 4 6 1 4 5 1 2 5 7 6 3 2
31 13 13 31 21 31 31