Problem 2377. -- [Noip模拟]树上的颜色

2377: [Noip模拟]树上的颜色

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

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

Input

第一行包含两个正整数N和M。
第二行包含N个正整数,C1,C2,…,CN。
接下来的N-1行每行有两个正整数x和y,表示结点x和y有边相连。
再接下来的M行每行有两个正整数u和k,表示一个询问。
N≤100000,M≤100000,Ci≤100000。

Output

输出M行,每行一个非负整数,对应每个询问的答案。

Sample Input

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

Sample Output

4

HINT

Source

[Submit][Status]