题目描述

你有一棵由 $n$个顶点组成的有根树。树的每个顶点都有一种颜色。我们假设树的顶点按照从 $1$ 到 $n$ 的整数编号。然后我们将顶点 $v$ 的颜色表示为 $c_v$。树的根是编号为 $1$ 的顶点。

你需要回答 $m$个查询。每个查询由两个整数 $v_j,k_j$ 描述。对于查询的 $v_j,k_j$ 答案是这样的颜色的顶点 $x$ 的数量，使得顶点 $v_j$ 的子树包含至少 $k_j$ 个颜色为 $x$ 的顶点。

输入格式

第一行包含两个整数 $n$ 和 $m$。

下一行包含整数序列 $c_1,c_2,\ldots,c_n$。接下来的 $n-1$ 行包含树的边。第 $i$ 行包含数字 $a_i,b_i$ ( $1 \le a_i,b_i \le n$，$a_i \ne b_i$)，表示树中连接的两个顶点。

接下来的 $m$ 行包含查询。第 $j$ 行包含两个整数 $v_j,k_j$ ( $1 \le v_j \le n$ ，$1 \le k_j \le 10^5$ )。

输出格式

对于每个操作，输出其结果。

8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3

2
2
1
0
1

样例分析

第一个询问，节点 $1$ 为根的子树，有颜色 $2$ 和颜色 $3$ 两种颜色的子节点个数 $\ge 2$；

第二个询问，节点 $1$ 为根的子树，有颜色 $2$ 和颜色 $3$ 两种颜色的子节点个数 $\ge 3$；

第三个询问，节点 $1$ 为根的子树，有颜色 $3$ 一种颜色的子节点个数 $\ge 4$；

第四个询问，节点 $2$ 为根的子树，没有一种颜色的子节点个数 $\ge 3$；

第五个询问，节点 $5$ 为根的子树，有颜色 $3$ 一种颜色的子节点个数 $\ge 3$。

数据范围与提示

对于 $100\%$ 的数据：$2 \le n \le 10^5$ ，$1 \le m \le 10^5$，$1 \le c_i \le 10^5$。