파이몬의 나무

파이몬은 처음에 흰색인 정점 $(n + 1)$개로 이루어진 나무를 왼쪽 주머니에서 찾아 가지고 놀기로 한다. 정점이 $(n + 1)$개인 나무는 간선이 $n$개인 연결된 무방향 그래프이다.

파이몬이 길이 $n$인 정수 수열 $a_1, a_2, \cdots, a_n$을 준다. 먼저 나무에서 정점 하나를 골라 검은색으로 칠한다. 그다음 아래 연산을 $n$번 수행한다.

$i$번째 연산에서는 검은색 정점 $y_i$와 간선으로 직접 연결된 흰색 정점 $x_i$를 하나 고른다. 그 간선의 가중치를 $a_i$로 정하고, $x_i$를 검은색으로 칠한다. $n$번의 연산이 끝나면 모든 간선에 가중치가 있는 나무가 남는다.

정점을 최적으로 고를 때, 가중치가 있는 나무 지름의 최댓값은 얼마인가? 나무의 지름은 가장 긴 단순 경로이고, 경로의 길이는 그 경로에 있는 간선 가중치의 합이다.

입력은 여러 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 5 \times 10^3$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 수열의 길이 $n$ ($1 \le n \le 150$)이 주어진다.

둘째 줄에 정수 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$)이 주어진다.

다음 $n$개 줄의 $i$번째 줄에는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n + 1$)가 주어진다. 이는 정점 $u_i$와 $v_i$를 잇는 간선이 있다는 뜻이다.

$n > 20$인 테스트 케이스는 최대 10개라고 보장된다.

각 테스트 케이스마다 가중치가 있는 나무 지름의 최댓값을 한 줄에 출력한다.

첫 번째 테스트 케이스에서는 $1, 3, 4, 5, 2, 6$ 순서로 정점을 고른다. 이렇게 만들어진 가중치 나무는 아래 그림과 같고, 가장 긴 단순 경로의 길이는 $16$이다.