P13263 [GCJ 2014 #3] Willow

Hanaa and Sherine are playing Willow, a game that is played on a board containing $\mathbf{N}$ cities. The $\mathrm{i}^{\text {th }}$ city contains $\mathbf{C}_{\mathrm{i}}$ coins, and there are $\mathbf{N}-1$ bidirectional roads running between the cities. All cities are reachable from one another. The game is played as follows: First Hanaa chooses one of the cities as her starting location, then Sherine chooses one of the cities (possibly the same one Hanaa chose) as her starting location. Afterwards, they take turns playing the game, with Hanaa going first. On a player's turn, that player must take all the coins on the city where she currently is, if there are any; there might be none if the city starts with no coins, or if one of the players has already started a turn in that city. Then, if possible, the player must travel to an adjacent city on a road. It might not be possible, because each road can be used at most once. This means that after one player has used a road, neither player is allowed to use the same road later. The game ends when neither Hanaa nor Sherine can make a move. After the game ends, each player's score is equal to the difference between the number of coins she has and the number of coins her opponent has. If her opponent has more coins, this means that her score will be negative. Both players are trying to maximize their scores. Assuming that they are both using the best possible strategy to maximize their scores, what is the highest score that Hanaa can obtain?

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case starts with a line containing one integer $\mathbf{N}$, the number of cities on the board. $\mathbf{N}$ lines then follow, with the $\mathrm{i}^{\text {th }}$ line containing an integer $\mathbf{C}_{\mathrm{i}}$, the number of coins in city $\mathrm{i}$. Finally there will be another $\mathbf{N}-1$ lines, with the $\mathrm{i}^{\text {th }}$ line $(\mathrm{i}$ starts from 1$)$ containing a single integer $\mathrm{j}(\mathrm{i}

For each test case, output one line containing "Case #x: $y$", where $\mathrm{x}$ is the case number (starting from 1) and $y$ is the highest score that Hanaa can obtain.

**Limits** - Memory limit: 1 GB. - $1 \leq \mathbf{T} \leq 50 .$ - $0 \leq \mathbf{C}_{\mathrm{i}} \leq 10000 .$ **Small dataset(15 Pts)** - Time limit: ~~60~~ 30 seconds. - $2 \leq \mathbf{N} \leq 80 .$ **Large dataset(24 Pts)** - Time limit: ~~120~~ 30 seconds. - $2 \leq \mathbf{N} \leq 500 .$