小松鼠的聚会(Squirrel Gathering)

题目描述

第十五届蓝桥STEMA青少年组2023年12月C++组第6题

在一片树林中，有 $n$ 个树洞，按顺序从 $1$ 到 $n$ 编号，每个树洞里住着至少一只松鼠。一条藤蔓连接两个树洞，共有 $n -1$ 条藤蔓，使得任意两个树洞可以直接或间接到达。这些小松鼠经常举办聚会，当某个树洞中的小松鼠举办聚会时，它们也会邀请距离自家树洞不超过k 条藤蔓范围的邻居们前来参加聚会请计算出每个树洞分别在举办聚会时，最多有多少只小松鼠参加聚会，并按照树洞编号从 $1$ 到 $n$ 依次输出结果。

例如：$n = 4$，表示有 $4$ 个树洞，$1$ 到 $4$ 号树洞中居住的小松鼠的数量分别为: $5、3、6、1$；共有 $3$ 条藤蔓，每条藤蔓连接两个树洞，分别为：$1$ 和 $2$、$1$ 和 $3$、$2$ 和 $4$;

$k = 2$，表示当某个树洞中的小松鼠举办聚会时，它们会邀请距离自家树洞不超过 $2$ 条藤蔓范围的邻居们前来参加聚会;

根据上图得知:

当 $1$ 号树洞的小松鼠举办聚会时，$1、2、3、4$ 号树洞中的小松鼠可以参加，最多会有 $15(5 +3 + 6+1)$ 只小松鼠参加;

当 $2$ 号树洞的小松鼠举办聚会时，$1、2、3、4$ 号树洞中的小松鼠可以参加，最多会有 $15(5 +3 + 6+1)$ 只小松鼠参加;

当 $3$ 号树洞的小松鼠举办聚会时，$1、2、3$ 号树洞中的小松鼠可以参加，最多会有 $14(5 +3+ 6)$ 只小松鼠参加;

当 $4$ 号树洞的小松鼠举办聚会时，$1、2、4$ 号树洞中的小松鼠可以参加，最多会有 $9(5+3+ 1)$ 只小松鼠参加；

故答案为:

15

15

14

9

输入格式

第一行输入一个整数 $n(1≤n<100000)$，表示树洞的数量。

接下来 $n$ 行，每行输入一个整数 $c_i(0\le c_i \le 1000)$，表示每个树洞中居住的小松鼠的数量

接下来 $n - 1$ 行，每行输入两个整数 $a_i,b_i(1\le a_i,b_i\le n)$，表示藤蔓连接两个树洞的编号，整数之间以一个空格隔开

最后一行输入一个整数 $k(1≤k≤20)$，表示邀请邻居的距离限制。

输出格式

共 $n$ 行，每行输出一个整数，表示每个树洞中的小松鼠在举办聚会时，参加聚会的小松鼠的最大数量，按照树洞编号从 $1$ 到 $n$ 依次输出结果。

样例输入 #1

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

样例输出 #1

15
15
14
9

数据范围

详见题目描述与输入格式中的数据规模约定。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接