[EHOI2023]贪吃的Zak

题目描述

Zak面前有$n$袋信仰，每袋信仰里都有$a_{i}$个锅巴，且有$n-1$条路经将信仰相连。

Zak想尽可能吃到最多的锅巴，但是Zak太挑剔了，当他吃了第$i$袋信仰之后，就不愿意再吃与第$i$袋距离在$k$以内的其他信仰了。

输入格式

第一行有两个整数$n$和$k$。

接下来$n$行给出一个整数$a_{i}$，表示第$i$袋信仰有$a_{i}$个锅巴。

接下来$n-1$行给出两个整数$u,v$，表示从$u$到$v$有一条边相连。

输出格式

输出一个整数，表示能吃到的最多的锅巴数 $mod$ $998244353$。

样例 #1

样例输入 #1

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

样例输出 #1

15

提示

对于100%数据， $1≤n≤20000,0≤k≤2,0≤|a_{i}|≤10^8$。