子树颜色数

题目描述

一棵以结点1为根的有根树，每个点上有颜色，有一些询问，每次询问以 𝑥 为根的子树有多少个颜色为k的点。$𝑛 ,𝑞 ≤ 10^5$。

输入格式

第一行二个整数n， q，表示树的结点数和询问的子树数,

接下来n-1行，每行一条边,

接下来一行n个数，表示每个结点的颜色c[i],

接下来q行表示询问的子树 和 颜色k。

输出格式

对于每个询问，输出该子树颜色k的点的数量。

样例 #1

样例输入 #1

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

样例输出 #1

1
1
0
1
0

提示

对于前三组数据，有 $1\leq q,c[i]\leq n\leq 100$，

而对于所有数据，有$1\leq q,c[i]\leq n\leq 10^5$。

Limitation

1s, 1024KiB for each test case.