P13263 [GCJ 2014 #3] Willow

Hanaa 和 Sherine 正在玩一款叫做 Willow 的游戏，这个游戏在一张包含 $\mathbf{N}$ 座城市的地图上进行。第 $\mathrm{i}$ 座城市中含有 $\mathbf{C}_{\mathrm{i}}$ 枚金币，城市之间通过 $\mathbf{N} - 1$ 条双向道路连接，保证任意两座城市之间都可以互相到达。 游戏规则如下： 首先，Hanaa 选择一座城市作为她的起始位置。接着，Sherine 也选择一座城市作为她的起始位置（可以选择与 Hanaa 相同的城市）。之后，她们轮流行动，由 Hanaa 先开始。 在每个玩家的回合中，她必须收走当前所在城市的所有金币（如果还有的话）；如果这座城市本来没有金币，或者金币已经在先前被某个玩家起始回合收走了，那么这一回合就不会获得金币。然后，如果可能的话，玩家必须沿着一条道路移动到相邻的城市。但要注意：**每条道路最多只能使用一次**，即一旦某条道路被任何一个玩家使用过，之后两人都不能再走这条路。若某位玩家无法移动，她的回合立即结束。 当 Hanaa 和 Sherine 都无法再行动时，游戏结束。 每位玩家的得分为自己获得的金币数减去对手获得的金币数。如果对手获得的金币更多，该玩家得分则为负数。两人都采用最优策略，目的是**最大化自己的得分**。 请你计算：在双方都采取最优策略的前提下，Hanaa 最多能获得多少分？

输入的第一行是测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。 每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示地图上的城市数量。 接下来的 $\mathbf{N}$ 行中，第 $i$ 行包含一个整数 $\mathbf{C}_{\mathrm{i}}$，表示第 $i$ 座城市的金币数。 之后是 $\mathbf{N} - 1$ 行，第 $i$ 行（$i$ 从 1 开始）包含一个整数 $j$，表示城市 $i$ 与城市 $j$ 之间有一条道路。保证图中所有城市最开始是连通的。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Hanaa 在最优对局中最多可以获得的分数。

## 限制条件 - 内存限制：1 GB - $1 \leq \mathbf{T} \leq 50$ - $0 \leq \mathbf{C}_{\mathrm{i}} \leq 10000$ ### Small 数据集（15 分） - 时间限制：~~60~~ 30 秒 - $2 \leq \mathbf{N} \leq 80$ ### Large 数据集（24 分） - 时间限制：~~120~~ 30 秒 - $2 \leq \mathbf{N} \leq 500$ 翻译由 ChatGPT-4o 完成