You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一棵 $n$ 个点的树 $T=(V,E)$，对每个点 $i$ 有点权 $g_i$，对于树上不同的点 $a,b,c\in V$，构成的有序三元组 $(a,b,c)$，按如下规则定义其价值 $f(a,b,c)$：

• 令 $x$ 为树上令 $\mathrm{dist}(x,a)-\mathrm{dist}(x,b)-\mathrm{dist}(x,c)$ 最大的点（如有多个，取编号最小的），其中 $\mathrm{dist}(x,y)$ 表示树上点 $x,y$ 之间简单路径经过的边数；
• $f(a,b,c)=\mathrm{dist}(x,a)+\mathrm{dist}(x,b)+\mathrm{dist}(x,c)$ 。

给定 $d$，你需要在树中选出三个不同的点 $L,C,W$，满足 $|g_L-g_C|\ge d,|g_L-g_W|\ge d$，输出 $f(L,C,W)$ 的最大值，无解输出 $-1$ 。

输入格式

第一行，输入两个整数，表示 $n, d$ $(3 \le n \le 5\times 10^5, 1 \le a_i, d \le 10^9)$；

第二行，输入 $n$ 个整数，表示 $g_1, g_2, \ldots, g_n$ $(1\le g_i \le 10^9)$ ；

以下 $n-1$ 行，每行输入两个整数 $u,v$ ，表示一条树上的边。

输出格式

输出一行一个整数，表示 $f(L, C, W)$ 的最大值；如果无解，输出 $-1$ 。

输入输出样例 #1

输入 #1

6 5
4 3 13 3 14 2 
1 2
1 3
1 4
1 5
2 6

输出 #1

6