Willow

Hanaa and Sherine play a game called Willow. The board has $N$ cities, city $i$ holds $C_i$ coins, and $N - 1$ two-way roads connect the cities so that every city can be reached from every other city.

Hanaa first picks a city to start from. Sherine then sees that choice and picks her own starting city, which may be the city Hanaa picked. After that the two take turns, Hanaa first.

On her turn a player takes every coin left in the city she is standing on. There is nothing to take if the city started empty, or if one of the players has already started a turn there. She then has to travel to a neighboring city along a road that has not been used yet. If no unused road leads out of her city, she stays where she is. Each road can be used at most once, so once one player has driven a road, the other cannot use it either. The game ends when neither player has a coin to take and neither can move.

When the game ends, each player's score is the number of coins she collected minus the number of coins her opponent collected. A player who collects fewer coins ends with a negative score. Both players maximize their own score. If both play as well as possible, what is the highest score Hanaa can get?

The first line has the number of test cases $T$. $T$ test cases follow.

The first line of each test case has the number of cities $N$. The $i$-th of the next $N$ lines has $C_i$, the number of coins in city $i$. The $i$-th of the following $N - 1$ lines ($i$ starts at 1) has a single integer $j$, which means that a road joins city $i$ and city $j$. Always $1 \le i < j \le N$, and every city can be reached from every other city when the game starts.

The limits are as follows.

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

For each test case, print one line Case #x: y, where $x$ is the test case number starting at 1 and $y$ is the highest score Hanaa can get.