Description

Hanaa 和 Sherine 正在玩一款叫做 Willow 的游戏，这个游戏在一张包含 $\mathbf{N}$ 座城市的地图上进行。第 $\mathrm{i}$ 座城市中含有 $\mathbf{C}_{\mathrm{i}}$ 枚金币，城市之间通过 $\mathbf{N} - 1$ 条双向道路连接，保证任意两座城市之间都可以互相到达。

游戏规则如下：

首先，Hanaa 选择一座城市作为她的起始位置。接着，Sherine 也选择一座城市作为她的起始位置（可以选择与 Hanaa 相同的城市）。之后，她们轮流行动，由 Hanaa 先开始。

在每个玩家的回合中，她必须收走当前所在城市的所有金币（如果还有的话）；如果这座城市本来没有金币，或者金币已经在先前被某个玩家起始回合收走了，那么这一回合就不会获得金币。然后，如果可能的话，玩家必须沿着一条道路移动到相邻的城市。但要注意：每条道路最多只能使用一次，即一旦某条道路被任何一个玩家使用过，之后两人都不能再走这条路。若某位玩家无法移动，她的回合立即结束。

当 Hanaa 和 Sherine 都无法再行动时，游戏结束。

每位玩家的得分为自己获得的金币数减去对手获得的金币数。如果对手获得的金币更多，该玩家得分则为负数。两人都采用最优策略，目的是最大化自己的得分。

请你计算：在双方都采取最优策略的前提下，Hanaa 最多能获得多少分？

Input Format

输入的第一行是测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。

每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示地图上的城市数量。

接下来的 $\mathbf{N}$ 行中，第 $i$ 行包含一个整数 $\mathbf{C}_{\mathrm{i}}$，表示第 $i$ 座城市的金币数。

之后是 $\mathbf{N} - 1$ 行，第 $i$ 行（$i$ 从 1 开始）包含一个整数 $j$，表示城市 $i$ 与城市 $j$ 之间有一条道路。保证图中所有城市最开始是连通的。

Output Format

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

3
3
1000
200
1000
2
3
8
8
0
8
0
0
0
0
10
2
5
4
5
6
7
8
10
150
200
0
5000
0
100
0
0
0
10000
10
3
8
5
8
7
8
9
10

Case #1: 200
Case #2: -2
Case #3: 5100

Hint

限制条件

• 内存限制：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 完成