P16899 [GKS 2022 #H] Electricity

Ben 在一座拥有 $N$ 个电力节点的城市中担任工程师。这些节点构成一个网络，可以看作是一个具有 $N$ 个顶点和 $N-1$ 条边的连通图。城市正面临停电，所有节点都没有电力供应，Ben 负责处理这一情况。 每个节点都有一个固定的电容量。$A_i$ 是第 $i$ 个节点的电容量。由于资源限制，Ben 只能为其中一个节点供电，但其他节点可以根据其连接和电容量接收电力。如果第 $i$ 个节点接收到电力，那么它会将电力传输到所有与它直接相连且电容量**严格小于** $A_i$ 的节点。当没有符合条件的节点时，传输停止。请帮助 Ben 确定最多有多少个节点可以接收到电力。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N$，表示城市中节点的数量。 第二行包含 $N$ 个整数。其中第 $i$ 个整数是 $A_i$，表示第 $i$ 个节点的电容量。 接下来的 $N-1$ 行，每行包含两个整数 $X_i$ 和 $Y_i$，表示节点 $X_i$ 和 $Y_i$ 直接相连。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是能够接收到电力的最大节点数。

:::align{center}  ::: 在样例 #1 中，最优方案是为第 $4$ 个节点供电。电力最终会传输到所有节点。 如果为第 $3$ 个节点供电，它会将电力传输到第 $1$ 个和第 $2$ 个节点，但不会传输到第 $4$ 个节点。在这种情况下，最终只有三个节点能接收到电力。 :::align{center}  ::: 在样例 #2 中，最优方案是为第 $3$ 个节点供电。它会将电力传输到第 $1$ 个和第 $2$ 个节点。注意，电力不会传输到第 $4$ 个节点，因为它的电容量不小于第 $3$ 个节点的电容量。 如果为第 $6$ 个节点供电，它只会传输到第 $1$ 个节点。 如果为第 $4$ 个节点供电，它只会传输到第 $5$ 个节点。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le A_i \le 10^9$。 对于所有 $i$，$1 \le X_i, Y_i \le N$。 所有节点属于同一个连通网络。 **测试集 1** $1 \le N \le 10^3$。 **测试集 2** 最多 $15$ 个测试用例满足： $1 \le N \le 2 \times 10^5$。 其余测试用例满足： $1 \le N \le 10^3$。 翻译由 DeepSeek V4 Pro 完成