8435: Nearby Cows

Farmer John has noticed that his cows often move between nearby fields. Taking this into account, he wants to plant enough grass in each of his fields not only for the cows situated initially in that field, but also for cows visiting from nearby fields. Specifically, FJ's farm consists of N fields (1 <= N <= 100,000), where some pairs of fields are connected with bi-directional trails (N-1 of them in total). FJ has designed the farm so that between any two fields i and j, there is a unique path made up of trails connecting between i and j. Field i is home to C(i) cows, although cows sometimes move to a different field by crossing up to K trails (1 <= K <= 20). FJ wants to plant enough grass in each field i to feed the maximum number of cows, M(i), that could possibly end up in that field -- that is, the number of cows that can potentially reach field i by following at most K trails. Given the structure of FJ's farm and the value of C(i) for each field i, please help FJ compute M(i) for every field i.

农夫约翰注意到他的奶牛经常在附近的田野之间徘徊。

考虑到这一点，他希望在每片田地中都种上足够多的草，使得每片田地都既能满足居住在此田地的奶牛的吃草需求，也能满足从附近田地来访的奶牛的吃草需求。

具体地说，约翰的农场由 N 片田地组成，其中一些田地对之间由双向道路直接相连（共 N−1 条道路）。

已知，任意两片田地之间都存在一条唯一的连通路径。

田地 i 中居住有 Ci 头奶牛。

奶牛们有时会走过不超过 K 条道路，到另一片田地游玩。

约翰希望每片田地 i 中都能种植足够多的草，以满足可能在该田地中出现的最大数量（用 Mi 表示）的奶牛的吃草需求。

显然，每片田地中可能出现的奶牛的最大数量即为能够通过不超过 K 条道路到达该田地的奶牛（也包括住在该田地的奶牛）数量。

给定农场的结构以及每片田地 i 的 Ci 值，请帮助约翰计算每片田地 i 的 Mi 值。

输入格式

第一行包含两个整数 N 和 K。

接下来 N−1 行，每行包含两个整数 i 和 j，表示田地 i 和 j 之间由一条双向道路直接相连。

接下来 N 行，其中第 i 行包含整数 Ci。

共 N 行，第 i 行输出 Mi。

1≤N≤105,

1≤K≤20,

1≤i,j≤N,

0≤Ci≤1000