Bò Lân Cận

Nông trại của Farmer John có $N$ đồng cỏ được kết nối bởi $N-1$ con đường tạo thành một cái cây. Mỗi đồng cỏ $i$ có $C_i$ con bò đang gặm cỏ trên đó.

Farmer John muốn biết, với mỗi đồng cỏ $i$, có bao nhiêu con bò đang ở trong khoảng cách $K$ cạnh tính từ đồng cỏ $i$ (bao gồm cả bò trên chính đồng cỏ $i$).

Dữ liệu vào

• Dòng đầu tiên: hai số nguyên $N$ và $K$.
• $N-1$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $u$ và $v$ mô tả một con đường nối đồng cỏ $u$ và $v$.
• $N$ dòng tiếp theo: dòng thứ $i$ trong số này chứa số nguyên $C_i$ — số bò tại đồng cỏ $i$.

Dữ liệu ra

In ra $N$ dòng. Dòng thứ $i$ chứa $M_i$ — tổng số bò trong khoảng cách $K$ cạnh tính từ đồng cỏ $i$.

Ràng buộc

• $1\le N\le 100000$
• $1\le K\le 20$
• $0\le C_i\le 1000$

Ví dụ

Ghi chú

Đồng cỏ $u$ và $v$ có khoảng cách $d$ nếu đường đi ngắn nhất trên cây từ $u$ đến $v$ đi qua $d$ cạnh.