# Tree and Queries

## 题意翻译

- 给定一棵 \$n\$ 个节点的树，根节点为 \$1\$。每个节点上有一个颜色 \$c_i\$。\$m\$ 次操作。操作有一种： 1. `u k`：询问在以 \$u\$ 为根的子树中，出现次数 \$\ge k\$ 的颜色有多少种。 - \$2\le n\le 10^5\$，\$1\le m\le 10^5\$，\$1\le c_i,k\le 10^5\$。

## 题目描述

You have a rooted tree consisting of \$ n \$ vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to \$ n \$ . Then we represent the color of vertex \$ v \$ as \$ c_{v} \$ . The tree root is a vertex with number 1. In this problem you need to answer to \$ m \$ queries. Each query is described by two integers \$ v_{j},k_{j} \$ . The answer to query \$ v_{j},k_{j} \$ is the number of such colors of vertices \$ x \$ , that the subtree of vertex \$ v_{j} \$ contains at least \$ k_{j} \$ vertices of color \$ x \$ . You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree\_(graph\_theory).

## 输入输出格式

### 输入格式

The first line contains two integers \$ n \$ and \$ m \$ \$ (2<=n<=10^{5}; 1<=m<=10^{5}) \$ . The next line contains a sequence of integers \$ c_{1},c_{2},...,c_{n} \$ \$ (1<=c_{i}<=10^{5}) \$ . The next \$ n-1 \$ lines contain the edges of the tree. The \$ i \$ -th line contains the numbers \$ a_{i},b_{i} \$ \$ (1<=a_{i},b_{i}<=n; a_{i}≠b_{i}) \$ — the vertices connected by an edge of the tree. Next \$ m \$ lines contain the queries. The \$ j \$ -th line contains two integers \$ v_{j},k_{j} \$ \$ (1<=v_{j}<=n; 1<=k_{j}<=10^{5}) \$ .

### 输出格式

Print \$ m \$ integers — the answers to the queries in the order the queries appear in the input.

## 输入输出样例

### 输入样例 #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
``````

## 说明

A subtree of vertex \$ v \$ in a rooted tree with root \$ r \$ is a set of vertices \$ {u :dist(r,v)+dist(v,u)=dist(r,u)} \$ . Where \$ dist(x,y) \$ is the length (in edges) of the shortest path between vertices \$ x \$ and \$ y \$ .