CF375D Tree and Queries

题目描述

给定一棵以 $1$ 号顶点为根的有根树，树中共有 $n$ 个顶点。每个顶点 $v$ 有一个颜色 $c_v$。

你需要回答 $m$ 个询问。每个询问给出两个整数 $v,k$，要求统计：

在以 $v$ 为根的子树中，有多少种颜色出现次数不少于 $k$。

注意，询问中的“子树”均以 $1$ 号顶点为根所确定的父子关系为准。

输入格式

第一行两个整数 $n,m$，表示顶点数和询问数。

第二行 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示每个顶点的颜色。

接下来 $n-1$ 行，每行两个整数 $a,b$，表示树中的一条无向边。

接下来 $m$ 行，每行两个整数 $v,k$，表示一次询问。

输出格式

对每个询问输出一行一个整数，表示满足条件的颜色种数。

样例

样例输入

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\le n,m\le 10^5$，$1\le c_i\le 10^5$，$1\le v\le n$，$1\le k\le n$。