Willow (큰 입력)

Hanaa와 Sherine이 도시 $N$개로 이루어진 판 위에서 Willow라는 게임을 한다. $i$번 도시에는 동전이 $C_i$개 있고, 도시 사이에는 양방향 도로가 $N - 1$개 놓여 있다. 어느 도시에서든 다른 모든 도시로 갈 수 있다.

게임은 이렇게 진행한다. 먼저 Hanaa가 시작 도시를 하나 고르고, 그다음 Sherine이 시작 도시를 하나 고른다. Sherine은 Hanaa가 고른 도시를 그대로 골라도 된다. 그 뒤로는 Hanaa부터 시작해 번갈아 차례를 가진다.

자기 차례가 된 사람은 지금 서 있는 도시에 남아 있는 동전을 모두 가져가야 한다. 그 도시에 처음부터 동전이 없었거나 둘 중 한 명이 이미 그 도시에서 차례를 시작한 적이 있으면 가져갈 동전이 없다. 동전을 가져간 다음에는 도로로 이어진 이웃 도시로 이동해야 한다. 쓸 수 있는 도로가 하나도 남지 않았을 때만 그 자리에 머문다. 각 도로는 게임 전체에서 한 번만 쓸 수 있어서, 한 사람이 쓴 도로는 그 뒤로 두 사람 모두 쓸 수 없다. 이동할 수 없는 사람에게도 차례는 계속 돌아오고, 그 차례에 서 있는 도시의 동전을 가져간다. 두 사람 모두 이동할 수 없게 되면 게임이 끝난다.

게임이 끝나면 각자의 점수는 자기가 가진 동전 수에서 상대가 가진 동전 수를 뺀 값이다. 상대가 동전을 더 많이 가졌으면 점수는 음수가 된다. 두 사람 모두 자기 점수를 최대로 만들려고 최선을 다한다. Hanaa가 얻을 수 있는 가장 높은 점수는 얼마인가?

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

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

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

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