题目描述

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$ 是能够接收到电力的最大节点数。

2
5
1 2 3 4 3
1 3
2 3
4 3
4 5
6
1 2 3 3 1 4
3 1
3 2
3 4
4 5
1 6

Case #1: 5
Case #2: 3

提示

:::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 完成