题目描述

给定一棵由$n$个结点构成的树，结点编号为$1$～$n$，其中第$i$个点的点权为$a_i$。

请你分别对每个结点求出，与该结点距离不超过$d$的所有结点中点权最大值是多少？

输入格式

输入第一行：两个正整数$n,d$ 输入第二行：$n$个正整数$a_1,a_2,...,a_n$，分别表示每个点的点权。 接下来$n-1$行，每行两个正整数$u_i,v_i$，表示第$i$条边连接$u_i,v_i$两点。

输出格式

输出一行，$n$个整数，以空格隔开，其中第$i$个数字表示距离$i$号结点不超过$d$的所有结点中的最大值。

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

7 5 7 7 7 6

数据范围

• 对于$30\%$的数据，$1\leq n \leq 100$；

• 对于$60\%$的数据，$1\leq n \leq 10^4$；

• 对于$100\%$的数据，$1\leq n \leq 10^5, 1\leq d \leq 20,1\leq a_i \leq 10^9$