Willow

Hanaa와 Sherine은 N개의 도시가 있는 보드에서 진행되는 게임인 Willow를 하고 있다. i^{th} 도시에는 $C_{i}$개의 동전이 있으며, 도시 사이에는 N - 1개의 양방향 도로가 놓여 있다. 모든 도시는 서로 도달할 수 있다. 게임은 다음과 같이 진행된다.

먼저 Hanaa가 도시 중 하나를 자신의 시작 위치로 선택한 다음, Sherine이 도시 중 하나를 자신의 시작 위치로 선택한다(Hanaa가 선택한 도시와 같을 수도 있다). 그 후 Hanaa부터 시작하여 번갈아 게임을 진행한다.

자신의 차례가 되면 플레이어는 현재 있는 도시에 동전이 있다면 그 동전을 모두 가져가야 한다. 해당 도시에 처음부터 동전이 없거나, 플레이어 중 한 명이 이미 그 도시에서 차례를 시작한 적이 있다면 동전이 하나도 없을 수도 있다. 그런 다음 가능하다면 플레이어는 도로를 따라 인접한 도시로 이동해야 한다. 각 도로는 최대 한 번만 사용할 수 있으므로 이동이 불가능할 수도 있다. 즉, 한 플레이어가 도로를 사용한 후에는 어느 플레이어도 나중에 같은 도로를 사용할 수 없다. Hanaa와 Sherine 모두 이동할 수 없게 되면 게임이 끝난다.

게임이 끝난 후 각 플레이어의 점수는 자신이 가진 동전 수에서 상대가 가진 동전 수를 뺀 값이다. 상대가 더 많은 동전을 가지고 있다면 그 플레이어의 점수는 음수가 된다. 두 플레이어 모두 자신의 점수를 최대화하려 한다. 두 플레이어 모두 자신의 점수를 최대화하기 위한 최선의 전략을 사용한다고 가정할 때, Hanaa가 얻을 수 있는 가장 높은 점수는 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 50. 0 ≤ $C_{i}$ ≤ 10000.

작은 데이터 세트

시간 제한: 60초. 2 ≤ N ≤ 80.

큰 데이터 세트

시간 제한: 120초. 2 ≤ N ≤ 500.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 보드에 있는 도시의 수를 나타내는 정수 N이 담긴 줄로 시작한다. 그다음 N개의 줄이 주어지며, i^{th} 줄에는 도시 i의 동전 수를 나타내는 정수 $C_{i}$가 주어진다.

마지막으로 N - 1개의 줄이 더 주어지며, i^{th} 줄에는 도시 i와 도시 j 사이에 도로가 있음을 나타내는 하나의 정수 j (i < j ≤ N)가 주어진다. 여기서 i는 1부터 시작한다. 게임 시작 시 모든 도시가 서로 도달 가능함이 보장된다.

각 테스트 케이스마다 "Case #x: y"을 담은 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 Hanaa가 얻을 수 있는 가장 높은 점수이다.