题目内容

古镇准备办灯会。巷道连通 $n$ 个灯位，灯位编号 $1\sim n$。巷道没有环，任意两个灯位之间恰好有一条路可走，也就是说这 $n$ 个灯位和 $n-1$ 条巷道构成一棵树。

第 $i$ 个灯位挂灯后的预计人气收益为 $v_i$，可以为负

灯带必须沿着树上一连串巷道铺设，也就是树上的一条路径（可以只覆盖一个灯位）。每启动一条灯带，都要在路径的一端接入一个电箱，花费启动费 $C$。一条灯带的净收益为「它覆盖的灯位收益之和」减去 $C$。

$1.$电路容量有限，同一个灯位最多只能属于一条灯带，两条灯带不能共用任何一个灯位。

$2.$允许有的灯位不挂灯，也允许一条灯带都不铺。

$3.$不能把一条灯带铺成带分叉的连通块，只能是路径。

请给出可获得的最大总净收益。总净收益为各条灯带净收益之和；不铺灯带时按 $0$ 计。

输入描述

第一行两个整数 $n$、$C$。

第二行 $n$ 个整数 $v_1,v_2,\ldots,v_n$。

接下来 $n-1$ 行，每行两个整数 $u$、$v$，表示灯位 $u$ 与 $v$ 之间有一条巷道。

约束

$1 \le n \le 10^5$

$0 \le C \le 10^9$

$-10^9 \le v_i \le 10^9$

$1 \le u,v \le n$

保证给出的是一棵树

输出描述

输出一个整数：最大总净收益。

样例1

输入

3 5
10 10 10
1 2
2 3

输出

25

说明

三个灯位在一条巷道上。铺一条覆盖 $1-2-3$ 的灯带，净收益 $10+10+10-5=25$。

若拆成两条或三条短灯带，每条都要另付启动费，总收益更低。一条都不铺为 $0$，也不如 $25$。

样例2

输入

4 1
0 10 10 10
1 2
1 3
1 4

输出

28

说明

灯位 $1$ 连着三个叶子，不是一条路。四个灯位不能铺成一条灯带。

一种最优办法：用灯带 $2-1-3$ 覆盖两个叶子和中心（净收益 $10+0+10-1=19$），另一条灯带单独覆盖灯位 $4$（净收益 $10-1=9$），总和 $28$。第三个叶子也可以换成与中心、另一叶子组成路径，数值相同。

若三个叶子各铺一条、中心不挂，总和为 $27$，略差。