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.

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

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

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 $ .