J9 实践-8 树上数颜色3

题目描述

给出一棵有 $n$ 个点的有根树，结点编号为 $1,2,3,……,n$，根结点编号为 $1$，编号为 $i$ 的结点图上颜色 $c_i$。现在有 $m$个询问，每个询问要求求出以结点 $u$ 为根的子树上涂有此种颜色的结点个数不小于 $k$ 的颜色个数有多少。

输入格式

第一行包含两个正整数 $n$ 和 $m$。 第二行包含 $n$ 个正整数，$c_1,c_2,…,c_n$。 接下来的 $n-1$ 行每行有两个正整数 $x$ 和 $y$，表示结点 $x$ 和 $y$ 有边相连。 再接下来的 $m$ 行每行有两个正整数 $u$ 和 $k$，表示一个询问。

输出格式

输出 $m$ 行，每行一个非负整数，对应每个询问的答案。

样例输入

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

样例输出

4

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1\leq m,c[i]\leq n\leq 10000$。