Farmer John nhận thấy đàn bò của mình thường di chuyển giữa các cánh đồng gần nhau. Vì vậy, ông muốn trồng đủ cỏ trên mỗi cánh đồng không chỉ cho những con bò ban đầu ở đó, mà còn cho cả những con bò ghé sang từ các cánh đồng lân cận.

Cụ thể, trang trại của FJ gồm \(N\) cánh đồng (\(1 \leq N \leq 100\,000\)), trong đó một số cặp cánh đồng được nối với nhau bằng các đường mòn hai chiều (tổng cộng có \(N-1\) đường mòn). FJ đã thiết kế trang trại sao cho giữa hai cánh đồng bất kỳ \(i\) và \(j\) có đúng một đường đi gồm các đường mòn nối \(i\) với \(j\). Cánh đồng \(i\) là nơi ở của \(C(i)\) con bò, mặc dù đôi khi bò di chuyển sang một cánh đồng khác bằng cách đi qua không quá \(K\) đường mòn (\(1 \leq K \leq 20\)).

FJ muốn trồng đủ cỏ trên mỗi cánh đồng \(i\) để nuôi được số bò lớn nhất \(M(i)\) có thể xuất hiện tại đó, tức là số bò có khả năng đi tới cánh đồng \(i\) bằng cách đi qua nhiều nhất \(K\) đường mòn. Cho cấu trúc trang trại của FJ và giá trị \(C(i)\) của mỗi cánh đồng \(i\), hãy giúp FJ tính \(M(i)\) cho mọi cánh đồng \(i\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách, \(N\) và \(K\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(i\) và \(j\) (\(1 \leq i, j \leq N\)), cho biết cánh đồng \(i\) và cánh đồng \(j\) được nối trực tiếp bởi một đường mòn.
• \(N\) dòng cuối: dòng thứ \(N+i\) chứa số nguyên \(C(i)\) (\(0 \leq C(i) \leq 1000\)).

Dữ liệu ra

Với mỗi \(i\) từ \(1\) đến \(N\), dòng thứ \(i\) chứa giá trị \(M(i)\).

Ví dụ

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

15
21
16
10
8
11

Nguồn

USACO 2012 February Contest, Gold Division — Nearby Cows. Tác giả đề: Neal Wu và Eric Price (2011).

https://usaco.org/index.php?page=viewproblem2&cpid=120