Paimon's Tree

Paimon found a tree with $(n + 1)$ initially white vertices in her left pocket and decided to play with it. A tree with $(n + 1)$ nodes is a connected undirected graph with $n$ edges.

Paimon gives you an integer sequence $a_1, a_2, \cdots, a_n$ of length $n$. First, select a vertex of the tree and paint it black. Then perform the following operation $n$ times.

During the $i$-th operation, select a white vertex $x_i$ that is directly connected to a black vertex $y_i$ by an edge. Set the weight of that edge to $a_i$, and paint $x_i$ black. After these $n$ operations, you get a tree whose edges all have weights.

If you select the vertices optimally, what is the maximum length of the diameter of the weighted tree? The diameter of a weighted tree is the longest simple path in the tree. The length of a simple path is the sum of the weights of the edges on that path.

There are multiple test cases. The first line contains an integer $T$ ($1 \le T \le 5 \times 10^3$), the number of test cases. Each test case is described as follows.

The first line contains an integer $n$ ($1 \le n \le 150$), 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$).

The next $n$ lines contain the edges. The $i$-th of these lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n + 1$), meaning that vertices $u_i$ and $v_i$ are connected by an edge.

It is guaranteed that at most 10 test cases satisfy $n > 20$.

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

In the first test case, the vertices are selected in the order $1, 3, 4, 5, 2, 6$. This produces the weighted tree shown in the image below. The longest simple path has length $16$.