P9846 [ICPC 2021 Nanjing R] Paimon's Tree

# 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$ 次操作后，我们会得到一棵每条边都有权值的树。 在最优的选择节点策略下，这颗树的直径最大是多少？一棵树的直径是这棵树中的最长简单路径的长度。一条简单路径的长度是这条路径中所有边的权值之和。

一次运行将会给出多个测试数据。输入的第一行包含一个整数 $T$ ，表示测试数据的组数。 对于每个测试数据： > 第一行包括一个整数 $n$ ，表示序列 $a$ 的长度。 > > 第二行包括 $n$ 个整数 $a_1,a_2,...,a_n$ ，表示序列 $a$ 的内容。 > > 在接下来的 $n$ 行中，第 $i$ 行包括两个整数 $u_i$ 与 $v_i$ ，表示在这棵树上 $u_i$ 与 $v_i$ 有一条连边。

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

* $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$ 。