markdown

D. 树与查询

你有一棵包含 $n$ 个顶点的有根树。树的每个顶点都有某种颜色。我们将树的顶点编号为 $1$ 到 $n$，并用 $c_v$ 表示顶点 $v$ 的颜色。树的根是编号为 $1$ 的顶点。

本题需要回答 $m$ 个查询。每个查询由两个整数 $v_j$ 和 $k_j$ 描述。对于查询 $v_j, k_j$，其答案是：在顶点 $v_j$ 的子树中，出现次数至少为 $k_j$ 的颜色种类数。

有根树的定义可参考以下链接：
http://en.wikipedia.org/wiki/Tree_(graph_theory)

输入

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^5$；$1 \le m \le 10^5$）。
第二行包含一个整数序列 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^5$）。
接下来的 $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$）。

输出

输出 $m$ 个整数，按查询在输入中出现的顺序依次输出每个查询的答案。

样例

样例输入 1

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

样例输出 1

2
2
1
0
1

样例输入 2

4 1
1 2 3 4
1 2
2 3
3 4
1 1

样例输出 2

4

注

在以 $r$ 为根的树中，顶点 $v$ 的子树定义为顶点集合 $\{u : \text{dist}(r, v) + \text{dist}(v, u) = \text{dist}(r, u)\}$，其中 $\text{dist}(x, y)$ 表示顶点 $x$ 和 $y$ 之间最短路径的长度（按边数计算）。