2910. 电
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 某城市有$ N$个电力节点，编号 $1∼N$。 这些电力节点形成的电力网络，可以看作一个$ N$ 个节点 $N-1$ 条边的连通图。 每个电力节点都有一个固定的电容，其中第 $i$个节点的电容为 $Ai$。 现在，可以选择其中一个节点进行供电，其它节点也可以根据实际连接以及具体电容情况接收电力。 具体来说，如果第$ i$个节点通电，那么它也可以将电力传输给其它所有与它**直接连接**且电容**严格小于$** Ai$ 的节点。 我们希望通过合理选择初始供电节点，从而使得尽可能多的节点能够通电。 请你计算并输出可以通电的最大节点数量。 ## 输入格式 第一行包含整数 $T$，表示共有 $T$组测试数据。 每组数据第一行包含整数 $N$。 第二行包含 $N$ 个整数$ A1,A2,\dots,AN$。 接下来 $N-1$ 行，每行包含两个整数 $Xi,Yi$表示节点$ Xi$和$ Yi$ 之间存在直接连接。 ## 输出格式 每组数据输出一个结果，每个结果占一行。 结果表示为$ `Case #x: y$`，其中 $x$为组别编号（从$ 1$开始），$y$为可以通电的最大节点数量。 ## 数据范围 $1\leT\le100$, $1\leAi\le109$, $1\leXi,Yi\leN$, 一个测试点内最多$ 15$ 组数据满足$ 1\leN\le2\times105$，其余数据满足 $1\leN\le103$。 ```in4 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 ``` ```out4 Case #1: 5 Case #2: 3 ``` ## 说明  在$ Case 1$ 中，最佳方案是给第$ 4$ 个节点供电，这样可以将电力传输到所有节点。 注意，如果给第$ 3$个节点供电，则电力只会传输至第 $1,2$ 个节点，而无法传输至第$ 4$ 个节点，这样只有三个节点可以通电。  在 $Case 2 $中，最佳方案是给第 $3$ 个节点供电，这样可以将电力传输至第 $1,2$个节点，但是无法传输至第 $4$ 个节点，因为$ A4$ 并不严格小于 $A3$。 注意，如果给第 $6$个节点供电，则电力只会传输至第$1$ 个节点，如果给第$ 4$ 个节点供电，则电力只会传输至第$ 5$个节点。