CF375D Tree and Queries

你有一棵有根树，共有 $n$ 个顶点，每个顶点都有一个颜色。我们假设这些顶点编号为 $1$ 到 $n$。将顶点 $v$ 的颜色记作 $c_{v}$。树的根为编号 $1$ 的顶点。 本题中你需要回答 $m$ 个询问。每个询问由两个整数 $v_{j},k_{j}$ 描述。对于每个询问 $v_{j},k_{j}$，你需要回答在以 $v_{j}$ 为根的子树中，有多少种颜色 $x$，使得这种颜色在该子树中出现的顶点数不少于 $k_{j}$。 关于有根树的定义，可以参考如下链接：http://en.wikipedia.org/wiki/Tree\_(graph_theory)。

第一行包含两个整数 $n$ 和 $m$，$2 \leq n \leq 10^{5}$，$1 \leq m \leq 10^{5}$。 第二行包含 $c_{1},c_{2},...,c_{n}$，$1 \leq c_{i} \leq 10^{5}$，依次表示每个顶点的颜色。 接下来 $n - 1$ 行，每行两个整数 $a_{i},b_{i}$，$1 \leq a_{i},b_{i} \leq n$，$a_{i} \neq b_{i}$，表示树中的一条边。 接下来的 $m$ 行，每行两个整数 $v_{j},k_{j}$，$1 \leq v_{j} \leq n$，$1 \leq k_{j} \leq 10^{5}$，表示一个询问。

输出 $m$ 个整数，按输入顺序依次给出每个询问的答案。

在以 $r$ 为根的有根树中，顶点 $v$ 的子树定义为：集合 $\{ u : dist(r,v)+dist(v,u)=dist(r,u) \}$，其中 $dist(x,y)$ 表示顶点 $x$ 和 $y$ 之间的最短路径长度（以边数计）。 由 ChatGPT 5 翻译