4085. 外卖

【题目描述】

Kreso最近找了份送外卖的兼职工作。

在A市有$n$家餐馆，编号为$1\sim n$。它们由恰好$n-1$条路相连，使得任意两家餐馆相互可达。每天，Kreso首先要花费$m$单位时间从这些餐馆取外卖。

Kreso最初位于$1$号餐馆。每$1$单位时间，他要么从所在餐馆取出外卖；要么移动到一个相邻的餐馆。注意，经过一个餐馆并不会取外卖，取外卖要单独花费$1$单位时间。

设$n$家餐馆的外卖价值分别是$a_1$到$a_n$。请问在这次取外卖的过程中，Kreso取得的所有外卖的价值之和最大是多少？

【输入格式】

第一行，两个正整数$n,m$。

第二行，$n$个用空格隔开的正整数$a_1,\cdots,a_n$。

接下来$n-1$行，每行两个整数$u,v$，表示有一条路连接$u$号餐馆和$v$号餐馆。

【输出格式】

输出一行，一个整数，表示答案。

【样例输入】

3 5
9 2 5
1 2
1 3

【样例输出】

14

【样例说明】

Kreso首先花费$1$单位时间取出$1$号餐馆外卖，然后花费$1$单位时间移动到$3$号餐馆，然后花费$1$单位时间取出$3$号餐馆外卖，剩余$2$单位时间无用。取得外卖价值之和为$9 + 5 = 14$。

【样例下载】

样例下载

【数据规模与约定】

对于$30\%$的数据，$1\leq n,m\leq 100$。

对于$100\%$的数据，$1\leq n,m\leq 500,1\leq u,v\leq n,1\leq a_i\leq 10^6$。