꽃의 나라

꽃의 나라에는 $n$개의 도시가 있고, $i$번째 도시에서는 $a_i$송이의 꽃이 자란다. 도로는 $n-1$개이며, $i$번째 도로는 도시 $u_i$와 $v_i$를 잇는다. 임의의 두 도시 사이에는 항상 경로가 있다.

나라에서는 꽃 전시회를 열려고 한다. 먼저 전시관을 지을 도시 $z$를 고른다. 그다음 정확히 $k$개의 도시 $x_1, x_2, \ldots, x_k$를 선택하고, 그 도시들의 꽃을 도시 $z$로 옮긴다.

주최 측은 도시 $x$가 선택되면 $x$에서 $z$까지 경로 위의 모든 도시도 선택되어야 한다고 정했다. 따라서 도시 $z$도 반드시 선택되어야 한다.

각 $z = 1, 2, \ldots, n$에 대해, 도시 $z$에 전시관을 지었을 때 옮길 수 있는 꽃의 최대 개수를 구하라.

첫 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le n \le 40\,000$, $1 \le k \le \min(n, 3000)$).

둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 5 \cdot 10^5$).

이어서 $n-1$개의 줄에 두 정수 $x$와 $y$가 주어진다 ($1 \le x, y \le n$, $x \ne y$). 이는 정점 $x$와 $y$ 사이에 간선이 있다는 뜻이다. 주어진 그래프는 트리임이 보장된다.

$f_1, f_2, \ldots, f_n$을 한 줄에 출력한다. $f_i$는 $z = i$일 때의 답이다.