가까운 소들

농부 존은 소들이 가까운 밭 사이를 자주 오간다는 것을 알게 되었다. 그래서 각 밭에는 원래 그 밭에 있던 소뿐만 아니라 근처 밭에서 찾아올 수도 있는 소까지 먹일 만큼 충분한 풀을 심으려고 한다.

농장은 $N$개의 밭($1 \le N \le 100{,}000$)으로 이루어져 있고, 양방향 길 $N-1$개가 밭들을 잇는다. 임의의 두 밭 사이에는 길로 이어진 경로가 정확히 하나만 존재하므로, 밭들은 하나의 트리를 이룬다. 밭 $i$에는 처음에 $C(i)$마리의 소가 있으며($0 \le C(i) \le 1000$), 소는 길을 최대 $K$개($1 \le K \le 20$)까지 건너 다른 밭으로 이동할 수 있다.

각 밭 $i$에 대해, 그곳에 모일 수 있는 소의 최대 수 $M(i)$를 구하자. 이는 밭 $i$까지의 거리(두 밭을 잇는 유일한 경로에 포함된 길의 개수)가 $K$ 이하인 모든 밭 $j$의 $C(j)$를 더한 값이다. 농장의 구조와 모든 $C(i)$가 주어질 때, 모든 밭에 대해 $M(i)$를 계산하라.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $K$.
• 둘째 줄부터 $N$번째 줄까지: 각 줄에 공백으로 구분된 두 정수 $i$와 $j$ ($1 \le i, j \le N$)가 주어지며, 밭 $i$와 밭 $j$가 하나의 길로 직접 연결되어 있음을 뜻한다.
• $N+1$번째 줄부터 $2N$번째 줄까지: $N+i$번째 줄에 정수 $C(i)$가 주어진다 ($0 \le C(i) \le 1000$).

• 첫째 줄부터 $N$번째 줄까지: $i$번째 줄에 밭 $i$로부터 거리 $K$ 이내에 있는 소의 수 $M(i)$를 출력한다.

첫 번째 예제에서는 밭이 $6$개이고, 길이 $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$로 연결되어 있으며, 밭 $i$에는 $C(i) = i$마리의 소가 있다. $K = 2$일 때 밭 $1$에는 길을 두 개 이하로 건너 밭 $1, 2, 3, 4, 5$에서 소가 모일 수 있고, 이들의 소는 모두 $1 + 2 + 3 + 4 + 5 = 15$마리이므로 $M(1) = 15$이다.