题目描述

FJ 注意到了他的奶牛经常在附近的田地移动。考虑到这个事情，他想要在每个田地里种足够的草，不仅是为了最初在那块地里的奶牛，也是为了从附近田地来的奶牛。

特别地，FJ 的农场由 $N(1 \leq N \leq 100000)$ 个田地组成，某些田地之间由双向道路连接（一共有 $N-1$ 条）。对于田地 $i$，它是 $C_i$ 头奶牛的家，尽管奶牛有时能经过最多 $K$ 条边去到其它田地。

FJ 想在任意一个田地 $i$ 中种足够的草去喂养最大数量的奶牛 $M_i$（最终可能到这块地的奶牛），即仅经过最多 $K(1 \leq K \leq 20)$ 条边到达这里的奶牛。给定农场的结构和任意一个田地的奶牛数量 $C_i$，请求出对于任意一个 $i$ 求出对应的 $M_i$。

输入格式

第一行两个正整数 $n,k$。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u,v$ 之间有一条边。

最后 $n$ 行，每行一个非负整数 $C_i$。

输出格式

输出 $n$ 行，第 $i$ 行一个整数表示 $m_i$。

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

15 
21 
16 
10 
8 
11 

提示

【样例解释】
有 $6$ 个田地，道路连接了 $(5,1),(3,6),(2,4),(2,1),(3,2)$。第 $i$ 个田地有 $C_i=i$ 头奶牛。有 $M_1=15$ 头奶牛与田地 $1$ 的距离不超过 $2$，等等。

【数据范围】
对于 $100\%$ 的数据：$1 \le N \le 10^5$，$1 \le K \le 20$，$0 \le C_i \le 1000$。