Willow (Large)

Hanaa and Sherine play Willow, a game on a board of $N$ cities. City $i$ holds $C_i$ coins, and $N - 1$ bidirectional roads run between the cities. Every city can be reached from every other city.

The game runs like this. Hanaa first picks one city as her starting location, then Sherine picks one city as her starting location. Sherine may pick the very city Hanaa picked. After that the two take turns, and Hanaa goes first.

On her turn a player must take every coin left in the city she is standing in. There is nothing to take if that city started with no coins, or if one of the two players has already started a turn there. After taking the coins she must travel to a neighboring city along a road. She stays where she is only when no road is left for her to use. Each road can be used once in the whole game, so a road one player has used is closed to both players afterwards. A player who cannot move still keeps getting her turns and takes the coins of the city she stands in. The game ends once neither Hanaa nor Sherine can move.

When the game ends, each player's score is her own coin count minus her opponent's coin count. The score is negative when the opponent holds more coins. Both players play to maximize their own score. What is the highest score Hanaa can get?

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

Each test case starts with a line containing the number of cities $N$. The next $N$ lines follow, and the $i$th of them contains $C_i$, the number of coins in city $i$. Then $N - 1$ lines follow, and the $i$th of them ($i$ starts from 1) contains one integer $j$ ($i < j \le N$), meaning that a road joins city $i$ and city $j$. Every city is reachable from every other city when the game starts.

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

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