윌로우

Hanaa와 Sherine이 윌로우(Willow)라는 게임을 한다. 게임판에는 도시가 $N$개 있고, $i$번 도시에는 동전이 $C_i$개 놓여 있다. 도시 사이에는 양방향 도로가 $N - 1$개 있으며, 어느 도시에서든 나머지 모든 도시로 갈 수 있다.

먼저 Hanaa가 출발할 도시를 하나 고른다. 그다음 Sherine이 그 선택을 보고 자기가 출발할 도시를 고르는데, Hanaa가 고른 도시를 그대로 골라도 된다. 그 뒤 Hanaa부터 번갈아 차례를 진행한다.

자기 차례가 되면 지금 서 있는 도시에 남아 있는 동전을 모두 가져간다. 그 도시에 처음부터 동전이 없었거나 이미 누군가 그 도시에서 차례를 시작했다면 가져갈 동전이 없다. 그다음 아직 쓰지 않은 도로가 남아 있으면 그중 하나를 따라 이웃 도시로 반드시 이동한다. 쓸 수 있는 도로가 없으면 그 자리에 머무른다. 도로는 하나당 한 번만 쓸 수 있어서, 한 사람이 지나간 도로는 다른 사람도 다시 쓸 수 없다. 두 사람 모두 가져갈 동전이 없고 이동도 할 수 없게 되면 게임이 끝난다.

게임이 끝나면 각자의 점수는 자기가 모은 동전 수에서 상대가 모은 동전 수를 뺀 값이다. 상대가 더 많이 모았으면 점수는 음수가 된다. 두 사람 모두 자기 점수를 최대로 만들려고 한다. 둘 다 최선을 다해 겨룰 때 Hanaa가 얻을 수 있는 점수의 최댓값을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다.

각 테스트 케이스의 첫 줄에는 도시의 수 $N$이 주어진다. 다음 $N$개 줄 가운데 $i$번째 줄에는 $i$번 도시에 놓인 동전 수 $C_i$가 주어진다. 이어지는 $N - 1$개 줄 가운데 $i$번째 줄($i$는 1부터 센다)에는 정수 $j$가 하나 주어지며, 이는 $i$번 도시와 $j$번 도시를 잇는 도로가 있다는 뜻이다. 항상 $1 \le i < j \le N$이고, 게임을 시작할 때 어느 도시에서든 나머지 모든 도시로 갈 수 있다.

제한은 다음과 같다.

• $1 \le T \le 50$
• $2 \le N \le 80$
• $0 \le C_i \le 10000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Hanaa가 얻을 수 있는 점수의 최댓값이다.