题目描述

给定一棵 $n$ 个点的树，点 $x$ 有权值 $a_x$。

求一条树上的简单路径 $u_1,u_2,\dots,u_k$ 使得 $k-\left(\max_{1\le i\le k} a_{u_i}\right)+\left(\min_{1\le i\le k} a_{u_i}\right)$ 最小。

换句话说，求一条简单路径，使得 长度 - 点权最大值 + 点权最小值 最小。

你只需要输出最小值即可。

输入格式

多测，第一行一个正整数 $t$ 表示数据组数。

接下来 $t$ 组数据，每组数据格式如下：

第一行一个正整数 $n$ 表示树的大小。

接下来一行 $n$ 个正整数，分别为 $a_1,\dots,a_n$。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示一条连接 $x,y$ 的边。

输出格式

对于每组数据，输出一行一个整数，为 长度 - 点权最大值 + 点权最小值 的最小值。

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

0
-1

提示

样例的两组数据的最优解分别是选择 $(2\to 5)$ 和 $(2\to 3)$。

对于 $20\%$ 的数据，$T=1,n\le 50$。

对于 $40\%$ 的数据，$T=1,n\le 5000$。

对于 $50\%$ 的数据，所有数据中 $n^2$ 之和 $\le 5\times 10^7$。

对于 $100\%$ 的数据，$T\le 10^5$，$n\le 10^5$，所有数据中 $n$ 之和 $\le 10^6$，$1\le a_i\le 10^6$。