考虑按照 $x$ 的大小分治。令 $S=\Theta(\sqrt n)$。

• 若 $x\le S$，枚举 $x$，对于一个修改 $(x,y)$，若将所有 $\mathrm{dep}_u \bmod x=y$ 的点 $u$ 按 DFS 序排序，则受影响的点是一段区间。由于询问的个数是 $O(m \sqrt n)$ 的，需要用 $O(\sqrt n)$ 区间加，$O(1)$ 单点询问的分块维护。
• 若 $x>S$，则一次修改只会影响 $O(\sqrt n)$ 种不同的深度，如果能够找到这些深度对应的区间，即可用 $O(1)$ 区间加，$O(\sqrt n)$ 单点询问的分块维护。

为了找到这些区间，我们只需要找到每个区间的左端点和右端点，方法是类似的，不妨考虑左端点。

建立一棵新的树，其中点 $u$ 的父亲为原树中满足 $\mathrm{dep}_v=\mathrm{dep}_u+1$ 且 $\mathrm{dfn}_v>\mathrm{dfn}_u$ 的 $\mathrm{dfn}_v$ 最小的点 $v$，若不存在则 $v=n+1$。那么原树 $u$ 的子树中深度为 $\mathrm{dep}_u+k$ 的 DFS 序最小的点即为新树中 $u$ 的 $k$ 级祖先。

对新树重链剖分即可 (注意重链剖分的 $O(\log n)$ 不影响整体复杂度)。

时间复杂度：$O((n+m)\cdot \sqrt n)$。