Description

Paimon's Tree

Translation

派蒙在她的左口袋中找到了一颗有 $(n+1)$ 个白色节点的树。一颗有 $(n+1)$ 个节点的树是一个有 $n$ 条边的无向连通图。

派蒙会给你一个长度为 $n$ 的整数序列 $a_1,a_2,...,a_n$ 。我们首先需要选择这棵树中的一个节点并将它涂黑。接下来进行以下操作 $n$ 次。

在第 $i$ 次操作中，我们选择一个与一个黑色节点 $y_i$ 直连的白色节点 $x_i$ ，将这条边的权值设为 $a_i$ ，并且将节点 $x_i$ 涂黑。

进行上述的 $n$ 次操作后，我们会得到一棵每条边都有权值的树。

在最优的选择节点策略下，这颗树的直径最大是多少？一棵树的直径是这棵树中的最长简单路径的长度。一条简单路径的长度是这条路径中所有边的权值之和。

Input Format

一次运行将会给出多个测试数据。输入的第一行包含一个整数 $T$ ，表示测试数据的组数。

对于每个测试数据：

第一行包括一个整数 $n$ ，表示序列 $a$ 的长度。

第二行包括 $n$ 个整数 $a_1,a_2,...,a_n$ ，表示序列 $a$ 的内容。

在接下来的 $n$ 行中，第 $i$ 行包括两个整数 $u_i$ 与 $v_i$ ，表示在这棵树上 $u_i$ 与 $v_i$ 有一条连边。

Output Format

对于每个测试数据，输出一行，表示这棵树在最优操作下的直径长度。

2
5
1 7 3 5 4
1 3
2 3
3 4
4 5
4 6
1
1000000000
1 2

16
1000000000

Hint

• $1\le T\le 5\times 10^3$
• $1\le n\le 150$
• $1\le a_i\le 10^9$
• $1\le u_i,v_i\le n+1$
• 保证每个样例中最多有 $10$ 组测试数据满足 $n>20$ 。