Farmer John thấy bò hay di chuyển giữa ruộng gần nhau. Ông muốn trồng đủ cỏ mỗi ruộng cho bò ban đầu và bò tới thăm.

Có $N$ ruộng ($1 \le N \le 100{,}000$), một số nối bởi đường hai chiều, tổng $N-1$. Giữa bất kỳ $i$, $j$ có đường đi duy nhất. Ruộng $i$ có $C(i)$ bò, đôi khi vượt tối đa $K$ đường ($1 \le K \le 20$) sang ruộng khác.

Mỗi $i$ cần nuôi tối đa $M(i)$ bò có thể tới: tất cả đạt tới qua không quá $K$ đường. Từ cấu trúc và mỗi $C(i)$ tính mọi $M(i)$.

Dữ liệu vào

• Dòng $1$: số nguyên $N$, $K$ cách nhau bằng dấu cách.

• Dòng $2\ldots N$: số nguyên $i$, $j$ cách nhau bằng dấu cách ($1 \le i,j \le N$), nối trực tiếp.

• Dòng $N+1\ldots2N$: dòng $N+i$ chứa số nguyên $C(i)$ ($0 \le C(i) \le 1000$).

Dữ liệu ra

• Dòng $1\ldots N$: dòng $i$ chứa $M(i)$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

15
21
16
10
8
11

Ghi chú

Có $6$ ruộng, đường $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$. Ruộng $i$ có $C(i)=i$ bò.

Ruộng $1$ có $M(1)=15$ bò cách không quá $2$ đường, v.v.

Tác giả bài toán: Neal Wu và Eric Price, 2011