题目描述

农夫约翰注意到他的奶牛经常在附近的田地之间移动。考虑到这一点，他想在他的每个田地里种植足够的草，不仅是为了最初位于该田地的奶牛，而且也为了从附近田地来的奶牛。

具体来说，$\red{FJ }$的农场由 $\red{N }$个田地组成（$\red{1 <= N <= 100,000）}$，其中一些田地对通过双向路径连接（总共 $\red{N-1 }$个）。$\red{FJ }$设计了农场，以便在任何两个田地 $\red{i }$ 和 $\red{j }$之间，有一条由连接 $\red{i }$和 $\red{j }$之间的小径组成的独特路径。田地 $\red{i }$是 $\red{C(i) }$头奶牛的家，尽管奶牛有时会通过 $\red{K }$条路径 $\red{(1 <= K <= 20) }$移动到不同的田地。

$\red{FJ }$想在每个田地 $\red{i }$种足够的草来喂养可能最终在该田地中的最大数量的奶牛 $\red{M(i) - }$即最多跟随可能到达田地 $\red{i }$的奶牛数量$\red{K }$步道。给定 $\red{FJ }$的农场结构和每个字段 $\red{i }$的 $\red{C(i) }$值，请帮助 $\red{FJ }$计算每个字段 $\red{i }$的 $\red{M(i)}$。

给你一棵 $\red{n }$个点的树，点带权，对于每个节点求出距离它不超过 $\red{k }$的所有节点权值和 $\red{m_i}$

输入格式

第 $\red{1 }$行：两个以空格分隔的整数 $\red{N }$和 $\red{K}$。

第 $\red{2..N }$行：每行包含两个以空格分隔的整数 $\red{i }$和 $\red{j (1 <= i,j <= N)，}$表示字段 $\red{i }$和 $\red{j }$由一条路径直接连接。

第 $\red{N+1..2N }$行：第 $\red{N+i }$行包含整数 $\red{C(i)}$。$\red{(0 <= C(i) <= 1000)}$ 。

输出格式

第 $\red{1..N }$行：第 $\red{i }$行应包含 $\red{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

提示

有 $\red{6 }$个字段，路径连接 $\red{(5,1)}$、$\red{(3,6)}$、$\red{(2,4)}$、$\red{(2,1) }$和 $\red{(3,2)}$。字段 $\red{i }$有 $\red{C(i) = i }$头奶牛。

字段 $\red{1 }$在 $\red{2 }$条小径的距离内有 $\red{M(1) = 15 }$头奶牛，依此类推。

对于 $\red{100\%}$的数据：$\red{1 \le n \le 10^5}$ ，$\red{1 \le k \le 20，}$$\red{0 \le c_i \le 1000}$