You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

烽火报信

题目描述

A国有$n$个城池，这些城池由$n-1$条道路连成一个整体。每个城池内有兵力驻守，第$i$座城池内的兵力有$m_i$。每座城池有一个烽火台，当这座城池受到攻击时，侦察兵会点燃烽火台，这个时候和这座城市距离在$k$以内的所有城池的兵力都会出发来支援这座城池。

现在A国国王想知道，当一个城池点燃烽火台时，这个城池能集中多少的兵力。当然，你需要对每个城池都分别求出这个兵力。

输入格式

第一行两个正整数 $n,k$。 接下来 $n-1$ 行，每行两个正整数 $u,v$，表示城池 $u$ 和城池 $v$ 之间有一条道路相连。 最后 $n$ 行，每行一个非负整数 $m_i$，表示城池内的兵力。

输出格式

输出 $n$ 行，第 $i$ 行一个整数表示该城池点燃烽火台时能集中到的兵力。

样例 #1

样例输入 #1

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

样例输出 #1

8
15
16
11
21
10

提示

样例解释1

对于1号城池，和它距离在2以内的点是2号和5号，所以1号城池最多能集结5+1+2=8的兵力。其他城池按同样的方法计算即可。注意能集结的兵力包括原本城池内的兵力。

数据范围

对于$40\%$的数据，$1\le n \le 1000$

对于另外$10\%$的数据，$k=1$

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