派蒙的树

【题目描述】

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

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

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

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

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

【输入格式】

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

对于每个测试数据：

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

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

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

【输出格式】

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

【样例输入】

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

【样例输出】

16
1000000000

【数据规模与约定】

大样例

对于 $100\%$ 的数据：$1 \le T \le 5\times 10^3, 1 \le n\le 200, 1 \le a_i \le 10^9, 1\le u_i,v_i\le n+1$。

·$Subtask1(20pts): n \le 20$。

·$Subtask2(20pts): n \le 80$。

·$Subtask3(20pts): n \le 150$。

·$Subtask4(40pts): 无特殊限制$。

保证每个样例中最多有 $10$ 组测试数据满足 $n>20$ 。数据有梯度。

【来源】

[ICPC2021 Nanjing R] Paimon's Tree。