题目描述

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

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

${FJ }$想在每个田地 ${i }$，种足够的草来喂养可能最终在该田地中的最大数量的奶牛 ${M_i - }$即通过最多${K }$步可能到达田地 ${i }$的奶牛数量。给定 ${FJ }$的农场结构和每个农场 ${i }$的 ${C_i }$值，请帮助 ${FJ }$计算每个农场 ${i }$的 ${M_i}$。

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

输入格式

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

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

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

输出格式

第 ${1..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 }$头奶牛。

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

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