[Usaco 2012 Feb]Nearby Cows

Farmer John 发现，奶牛经常会前往附近的草场吃草。因此，他希望在每个草场种植足够的牧草，不仅供该草场原有的奶牛食用，也供从附近草场前来的奶牛食用。

农场由 $N$ 个草场和 $N-1$ 条双向道路组成。任意两个草场之间都有且仅有一条简单路径。

第 $i$ 个草场原有 $C_i$ 头奶牛。每头奶牛最多可以经过 $K$ 条道路前往其他草场。对于每个草场 $i$，请计算最多可能到达该草场的奶牛数量 $M_i$，即所有与草场 $i$ 的距离不超过 $K$ 条道路的草场中的奶牛总数。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $K$。

接下来 $N-1$ 行，每行包含两个以空格分隔的整数 $i$ 和 $j$，表示草场 $i$ 与草场 $j$ 之间有一条双向道路。

接下来 $N$ 行，第 $i$ 行包含一个整数 $C_i$，表示草场 $i$ 原有的奶牛数量。

输出格式

输出 $N$ 行，第 $i$ 行包含一个整数 $M_i$，表示最多可能到达草场 $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

数据范围

• $1\le N\le 10^5$；
• $1\le K\le 20$；
• $1\le i,j\le N$；
• $0\le C_i\le 1000$；
• 草场之间共有 $N-1$ 条双向道路，且任意两个草场之间都有且仅有一条简单路径。

来源与许可

本题为 USACO 2012 February 试题「Nearby Cows」，题面与测试数据整理自 BZOJ 2591。

样例 1

输入

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

输出

15
21
16
10
8
11