P12411 抱月

记 $P(u,v)$ 表示树上从节点 $u$ 到节点 $v$ 依次经过的点组成的序列，包括 $u$ 和 $v$。 记 $dep_u$ 表示在以 $1$ 为树根时，节点 $u$ 的深度（根节点深度为 $0$）。 记 $\operatorname{LCA}(u,v)$ 为树上节点 $u$ 和 $v$ 在以 $1$ 为树根时的最近公共祖先。 抱月有一棵树，树根为 $1$，一共有 $n$ 个节点。其中第 $i$ 个节点的颜色是 $c_i$。她发现，对于一个节点 $x$ 和整数 $k$，如果将 $P(x,1)$ 中所有满足：$dep_y\equiv dep_x \pmod{k}$ 的 $y$ 都拿出来，这些 $y$ 是有意义的。 所以，你需要解决这样一个问题。给定 $m$ 次询问，每次两个整数 $x,k$，求**删掉** $P(x,1)$ 中所有满足 $dep_y\equiv dep_x \pmod{k}$ 的 $y$ 后，满足 $dep_z \le dep_x$ 的 $z$ 中不同 $c_z$ 的数量。**每次询问独立**，也就是说这次删的点在下一次询问会恢复。 如果不理解，请看样例解释。

第一行两个整数 $n,m$。 第二行 $n$ 个整数 $c_i$。 接下来 $n-1$ 行，每行两个整数 $u~v$，表示 $u~v$ 之间有连边。 接下来 $m$ 行，每行两个整数 $x_i~k_i$，表示询问。

共 $m$ 行，每行一个整数，表示答案。

对于所有测试数据，保证 $1 \le n,m,k_i \le 10^5$，$1 \le u,v,x_i \le n$，$0 \le c_i \le 10^5$。 | Subtask | 限制 | 分值 | | :----------: | :----------: | :----------: | | $0$ | $n,m \le 10^3$ | $10$ | | $1$ | $c_i$ 相同 | $4$ | | $2$ | $k_i > \max\limits_{j=1}^{n} dep_j$ | $16$ | | $3$ | $n,m \le 5\times 10^4$ | $30$ | | $4$ |无 | $40$ | **样例解释** 对于第 $1$ 个询问，满足条件的 $y$ 为：$1,3$。删掉之后，满足条件的 $z$ 为：$2,4$。其中 $c_1=2,c_4=8$，所以答案为 $2$。 对于第 $3$ 个询问，满足条件的 $y$ 为：$1,5$。删掉之后，满足条件的 $z$ 为：$2,3,4,6,9$。其中 $c_2=1,c_3=4,c_4=8,c_6=2,c_9=7$，所以答案为 $5$。