CF375D.Tree and Queries

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

你有一棵包含 $n$ 个顶点的有根树。树中每个顶点均具有某种颜色。我们假设树的顶点编号为 $1$ 到 $n$ 的整数。顶点 $v$ 的颜色记为 $c_v$。树的根节点为编号为 $1$ 的顶点。

本题中，你需要回答 $m$ 个查询。每个查询由两个整数 $v_j$、$k_j$ 描述。对于查询 $(v_j, k_j)$，其答案为：满足“以顶点 $v_j$ 为根的子树中，颜色为 $x$ 的顶点数量不少于 $k_j$”这一条件的颜色 $x$ 的种类数。

有根树的定义参见如下链接：http://en.wikipedia.org/wiki/Tree_(graph_theory)。

The first line contains two integers n and m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The next line contains a sequence of integers _c_1, _c_2, ..., c__n (1 ≤ c__i ≤ 105). 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 ≤ 105).

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$；$1 \leq m \leq 10^5$）。
下一行包含一个整数序列 $c_1, c_2, \dots, c_n$（$1 \leq c_i \leq 10^5$）。
接下来的 $n-1$ 行描述树的边。第 $i$ 行包含两个数 $a_i, b_i$（$1 \leq a_i, b_i \leq n$；$a_i \neq b_i$），表示树中一条边所连接的两个顶点。

接下来的 $m$ 行为查询。第 $j$ 行包含两个整数 $v_j, k_j$（$1 \leq v_j \leq n$；$1 \leq k_j \leq 10^5$）。

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

输出 m 个整数——即各查询的答案，按输入中查询出现的顺序输出。

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.

以 $r$ 为根的有根树中，顶点 $v$ 的子树是指满足 $\text{dist}(r, v) + \text{dist}(v, u) = \text{dist}(r, u)$ 的所有顶点 $u$ 构成的集合。其中 $\text{dist}(x, y)$ 表示顶点 $x$ 与 $y$ 之间最短路径的长度（以边数计）。