P16740 [GKS 2019 #F] Spectating Villages

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$ 是你能获得的最大被照亮村庄的美丽值之和。

在样例 #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 完成