题解：CF2129E Induced Subgraph Queries

看上去就一眼莫队，你可以轻松地在 $\mathcal O(\deg_u)$ 的复杂度内移动指针。

先说这个轻松怎么做到。不拿发现 $[1,n]$ 里选若干个数异或起来，你考虑每个二进制位都放 $1$。其实就是 $\mathcal O(n)$ 量级的，不超过 $2n-1$。

然后使用值域分块，就是 $[1,V]$ 分 $\sqrt V$ 段，然后维护每一段有多少数，显然直接修改就是 $\mathcal O(1)$，查询先暴力跳大段然后锁定到一个段里去枚举答案。这样修改 $\mathcal O(1)$ 查询 $\mathcal O(\sqrt V)$。

现在的问题是，如果一个度数很大的点反复横跳，就爆炸了。

我们考虑这样子修改莫队算法的分块部分：设 $p_i=\sum\limits_{j=1}^i \deg_i+1$，然后按 $\sqrt{p_n}$ 为块长分块，每一个 $i$ 就在第 $\frac{p_i}{\sqrt{p_n}}$ 这一块。

$+1$ 是为了避免 $0$ 度节点的干扰。

不难发现 $p_n$ 是 $\mathcal O(m)$ 级别的，这样我们大点独占一块，小点凑一起，这个复杂度显然是对的。

还有一种实现方法，我们把 $[1,n]$ 的邻域挨个拿出来，拼成新的序列，在新的序列上面莫队。更多相关可以参考国家集训队 2025 论文集里焦思源的论文『浅谈一类图上邻域相关问题』。

调了调块长，发现 $2\sqrt{p_n}$ 跑起来更快一点。