A6290. Welcome24ever 和田地
编程题
普及+/提高
知识点
题目描述
Welcome24ever 注意到了他的奶牛经常在附近的田地移动。考虑到这个事情，他想要在每个田地里种足够的草，不仅是为了最初在那块地里的奶牛，也是为了从附近田地来的奶牛。
特别地，Welcome24ever 的农场由 $N$ 个田地组成，某些田地之间由双向道路连接（一共有 $N-1$ 条），这些田地和道路构成一棵树。对于田地 $i$，它是 $C_i$ 头奶牛的家，尽管这些奶牛有时能经过最多 $K$ 条边去到其它田地。
Welcome24ever 想在任意一个田地 $i$ 中种足够的草去喂养可能到这块地的最多奶牛数 $M_i$，也就是所有与田地 $i$ 的距离不超过 $K$ 条边的田地中的奶牛总数。给定农场的结构以及每一个田地的奶牛数量 $C_i$，请你求出对于每一个 $i$ 对应的 $M_i$。
特别地，Welcome24ever 的农场由 $N$ 个田地组成，某些田地之间由双向道路连接（一共有 $N-1$ 条），这些田地和道路构成一棵树。对于田地 $i$，它是 $C_i$ 头奶牛的家，尽管这些奶牛有时能经过最多 $K$ 条边去到其它田地。
Welcome24ever 想在任意一个田地 $i$ 中种足够的草去喂养可能到这块地的最多奶牛数 $M_i$，也就是所有与田地 $i$ 的距离不超过 $K$ 条边的田地中的奶牛总数。给定农场的结构以及每一个田地的奶牛数量 $C_i$，请你求出对于每一个 $i$ 对应的 $M_i$。
输入格式
第一行包含两个正整数 $N, K$。
接下来 $N-1$ 行，每行两个正整数 $u, v$，表示在田地 $u$ 和 $v$ 之间有一条无向道路。
最后 $N$ 行，每行一个非负整数 $C_i$，表示田地 $i$ 上奶牛的数量。
接下来 $N-1$ 行，每行两个正整数 $u, v$，表示在田地 $u$ 和 $v$ 之间有一条无向道路。
最后 $N$ 行，每行一个非负整数 $C_i$，表示田地 $i$ 上奶牛的数量。
输出格式
输出 $N$ 行，第 $i$ 行输出一个整数 $M_i$，表示与第 $i$ 个田地的距离不超过 $K$ 条边的所有田地中的奶牛数量之和。
输入输出样例
输入 #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
说明/提示
## 说明/提示
【样例解释】
共有 $6$ 个田地，道路连接为 $(5,1)$、$(3,6)$、$(2,4)$、$(2,1)$、$(3,2)$。第 $i$ 个田地有 $C_i = i$ 头奶牛。可以计算出，与田地 $1$ 距离不超过 $2$ 条边的田地为 $1,2,3,5$，对应奶牛总数为 $1+2+3+5=11$，再加上距离为 $2$ 的田地 $4$（路径 $1-2-4$）上的 $4$ 头奶牛，总共为 $15$，即 $M_1=15$。其他 $M_i$ 类似计算。
【数据范围】
- 对于所有数据，$1 \le N \le 10^5$，$1 \le K \le 20$；
- $0 \le C_i \le 1000$；
- 给定的 $N$ 个田地和 $N-1$ 条道路构成一棵树。
【样例解释】
共有 $6$ 个田地，道路连接为 $(5,1)$、$(3,6)$、$(2,4)$、$(2,1)$、$(3,2)$。第 $i$ 个田地有 $C_i = i$ 头奶牛。可以计算出，与田地 $1$ 距离不超过 $2$ 条边的田地为 $1,2,3,5$，对应奶牛总数为 $1+2+3+5=11$，再加上距离为 $2$ 的田地 $4$（路径 $1-2-4$）上的 $4$ 头奶牛，总共为 $15$，即 $M_1=15$。其他 $M_i$ 类似计算。
【数据范围】
- 对于所有数据，$1 \le N \le 10^5$，$1 \le K \le 20$；
- $0 \le C_i \le 1000$；
- 给定的 $N$ 个田地和 $N-1$ 条道路构成一棵树。