题目描述

在西天取经的路上，孙悟空常常需要去寻找食物，而妖怪通常会乘机偷袭唐僧。孙悟空想在有可能路过的N个地方提前存储好食物。这样不止是他们师徒四人，附近居住的村民如果在紧急情况下，也可以去吃。
N（1 <= n <= 100，000)个地方，每两者之间有一条无向边连接（总共n-1条边）。第i个地方有是C(i)个村民居住，尽管村民们有时会通过k条路到达其他不同的地方（1<=k<=20）。
孙悟空想在每个地方存储够M(i)个人吃的食物。M(i)指能从其他地方经过最多k步就能到达这个地方的人数。
请帮助孙悟空计算每一个地方的M(i)。

输入格式：

第一行：n和k;
后面n-1行：i和j（两个地方）(1 <= i,j <= N);
之后n行：1..n每一个地方居住的村民C(i)(0 <= C(i) <= 1000)。

输出格式：

n行：每行M(i)表示需要存储的食物

输入样例#1：

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

输出样例#1：

15 
21 
16 
10 
8 
11