树上问题

题目描述

378QAQ 有一棵由 $n$ 个节点组成的无根树，节点编号从 $1$ 到 $n$，每个节点有一个正整数点权。

378QAQ 认为一个节点是美丽节点，当且仅当该节点作为根时，对于除根节点以外的所有节点，其点权都 不小于 其父亲节点的点权的 $\frac{1}{2}$。

请你计算出有多少个节点是美丽节点。

输入格式

本题包含多组测试数据。 第一行包含一个正整数 $t（1 ≤ t ≤ 10^4）$，表示数据组数。 对于每组数据： 第一行包含一个正整数 $n（1 ≤ n ≤ 10^5）$，表示节点数量。 第二行包含 $n$ 个正整数 $a_1, a_2, . . . , a_n（1 ≤ a_i ≤ 10^6）$，表示编号为 $i$ 的节点点权。 之后 $n − 1$ 行，每行包含两个正整数 $u, v（1 ≤ u，v ≤ n，u \neq v）$，表示无根树中存在一条连接节点 $u$ 和节点 $v$ 的边。 保证单个测试点中所有数据的 $∑n ≤ 10^5$。

输出格式

对于每组数据，输出一个非负整数，代表美丽节点的数量。

样例 #1

样例输入 #1

3
3
1 2 3
1 2
2 3
5
3 2 2 2 1
1 2
3 1
4 1
1 5
8
699 673 592 276 600 343 369 374
7 6
8 5
4 6
7 1
7 2
1 8
4 3

样例输出 #1

3
1
7

提示

对于第二组数据，树的形态如下:

只有节点 $5$ 是美丽节点。当节点 $5$ 作为根时，除根节点以外的各个节点与其父亲节点的点权关系如下：

• 节点 $1$ 的父亲节点为节点 $5$，二者点权有 $3 ≥ \frac{1}{2}$，满足要求。
• 节点 $2, 3, 4$ 的父亲节点为节点 $1$，节点 $2, 3, 4$ 的点权均有 $2 ≥ \frac{3}{2}$，满足要求。

因此节点 $5$ 是美丽节点。当其他任意节点作为根时，从上图可以看出节点 $5$ 的父亲节点始终为节点 $1$，由于 $1 < \frac{3}{2}$，不满足要求，所以其余节点均不是美丽节点。