Problem description

Janek podczas swojego startu w finale olimpiady informatycznej napotkał następujące zadanie.
Dane jest drzewo o n wierzchołkach. Każdy wierzchołek ma swoją wagę a_i. Należy znaleźć największą wartość ∑_ii ⋅ a_pi, gdzie ciąg p₁, p₂, …, p_n oznacza dowolną kolejność odwiedzania wierzchołków przez algorytm DFS.
Rozważmy następujący pseudokod:

p = []
odwiedzony = [0,0,...,0]
void dfs(v):
    dodaj v na koniec p
    weź dowolną permutację s wierzchołków u takich, że istnieje krawędź (u,v) oraz odwiedzony[u]==0
    dla wszystkich u należących do s:
        dfs(u)

Formalnie p₁, p₂, …, p_n jest permutacją, która może powstać poprzez wywołanie funkcji dfs(s) dla dowolnego wierzchołka startowego s.

Jak już wiesz z któregoś z poprzednich zadań, Janek rozwiązał to zadanie z olimpiady bez problemu, czy Ty też dasz radę?

Wejście

W pierwszym wierszu znajduje się T, liczba przypadków testowych.
Dla każdego przypadku testowego:
W pierwszym wierszu liczba całkowita n.
W drugim wierszu n dodatnich liczb całkowitych a₁, a₂, …, a_n, oznaczających wagi wierzchołków.
Potem w kolejnych n − 1 wierszach dwie liczby u i v opisujące krawędź między dwoma wierzchołkami w drzewie.
Graf na wejściu tworzy drzewo.

Wyjście

T wierszy, w każdym jedna liczba, odpowiedź do danego testu.

Ograniczenia

Liczba przypadków testowych spełnia 1 ≤ T ≤ 10⁴

1 ≤ n_i, ∑_in_i ≤ 2 ⋅ 10⁵

1 ≤ a_i ≤ 10⁶

1 ≤ u ≠ v ≤ n_i

Przykład

2
6
4 1 9 2 2 4
3 5
1 2
5 1
1 6
2 4
8
3 4 6 7 1 3 2 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8

97
148