题目描述

Kickstartia 的乡村由 $V$ 个村庄（编号为 $1$ 到 $V$）组成，并由 $V-1$ 条双向道路（编号为 $1$ 到 $V-1$）连接。第 $i$ 条道路连接村庄 $X_i$ 和 $Y_i$。每条道路恰好连接两个村庄，且没有两条道路连接同一对村庄。此外，在 Kickstartia 中，任意两个村庄之间有且仅有一条道路序列相连。

有些村庄比其他村庄更美丽。第 $i$ 个村庄的美丽值为 $B_i$。注意，村庄的美丽值可能为负数！

你将在一些村庄中建造灯塔。如果一个村庄本身建有灯塔，或者与它直接相连的村庄建有灯塔，则该村庄被照亮。

你可以建造任意数量（包括零个）的灯塔。问你能获得的被照亮村庄的美丽值之和最大为多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $V$，表示村庄的数量。第二行包含 $V$ 个整数，其中第 $i$ 个整数为 $B_i$，即第 $i$ 个村庄的美丽值。

随后 $V-1$ 行，第 $i$ 行给出 $X_i$ 和 $Y_i$，表示第 $i$ 条道路连接村庄 $X_i$ 和 $Y_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你能获得的最大被照亮村庄的美丽值之和。

3
9
-10 4 -10 8 20 30 -2 -3 7
1 4
2 4
4 3
9 4
9 8
7 5
6 7
7 9
4
-2 20 20 20
1 2
1 3
1 4
5
-5 -10 8 -7 -2
5 4
4 3
3 2
2 1

Case #1: 67
Case #2: 58
Case #3: 0

提示

在样例 #1 中，你可以在村庄 $2$ 和 $7$ 建造灯塔。这将照亮村庄 $2$、$4$、$5$、$6$、$7$ 和 $9$，美丽值之和为 $4 + 8 + 20 + 30 + (-2) + 7 = 67$。还有其他建造灯塔的方式也可达到该总和。

在样例 #2 中，你可以在村庄 $1$、$2$ 和 $3$ 建造灯塔。这将照亮村庄 $1$、$2$、$3$ 和 $4$，美丽值之和为 $(-2) + 20 + 20 + 20 = 58$。还有其他建造灯塔的方式也可达到该总和。

在样例 #3 中，最好的做法是不建任何灯塔！这样没有村庄被照亮，总和为 $0$。

限制条件

$1 \le T \le 100$。

$2 \le V \le 10^5$。

对于所有 $i$，$-10^5 \le B_i \le 10^5$。

对于所有 $i$，$1 \le X_i, Y_i \le V$。

对于所有 $i$，$X_i \ne Y_i$。

对于所有 $i \ne j$，$(X_i, Y_i) \ne (X_j, Y_j)$。

任意两个村庄之间有且仅有一条道路序列相连。

测试集 1（可见）

$1 \le V \le 15$。

测试集 2（隐藏）

$1 \le V \le 10^5$。

翻译由 DeepSeek V4 Pro 完成