[ICPC2021 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$ 。

Paimon has found a tree with $(n + 1)$ initially white vertices in her left pocket and decides to play with it. A tree with $(n + 1)$ nodes is an undirected connected graph with $n$ edges. Paimon will give you an integer sequence $a_1, a_2, \cdots, a_n$ of length $n$. We first need to select a vertex in the tree and paint it black. Then we perform the following operation $n$ times. During the $i$-th operation, we select a white vertex $x_i$ which is directly connected with a black vertex $y_i$ by an edge, set the weight of that edge to $a_i$ and also paint $x_i$ in black. After these $n$ operations we get a tree whose edges are all weighted. What's the maximum length of the diameter of the weighted tree if we select the vertices optimally? The diameter of a weighted tree is the longest simple path in that tree. The length of a simple path is the sum of the weights of all edges in that path.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 5 \times 10^3$) indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 150$) indicating the length of the sequence. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) indicating the sequence. For the following $n$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n + 1$) indicating that there is an edge connecting vertex $u_i$ and $v_i$ in the tree. It's guaranteed that there is at most $10$ test cases satisfying $n > 20$.

For each test case output one line containing one integer indicating the maximum length of the diameter of the tree.

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

16
1000000000

For the first sample test case, we select the vertices in the order of $1, 3, 4, 5, 2, 6$, resulting in the weighted tree of the following image. It's obvious that the longest simple path is of length $16$.