首先，这题肯定是求出每个联通块的 SG 值来做。

问题是怎么求。

如果第一步删根，那么转移到的状态的 SG 值为根节点所有子树的 SG 值的异或和。

否则，转移到的状态的 SG 值均为某个子树可以转移到的状态的 SG 值异或上其余子树的 SG 值。

一个 $n$ 个点的树，其 SG 值显然不超过 $n$。

假设我们可以维护出每个子树可以一步到达的 SG 值构成的集合，那么我们就要支持如下几种操作：

• 全部异或一个数。
• 集合合并。
• 查询 $\operatorname{mex}$。

使用线段树合并即可轻松实现这些功能。

总复杂度 $O(n\log n)$，可以轻松通过。

可以做到 $O(n)$ 空间，细节较为繁琐。

启发式合并 + 开桶也可以做到 $O(n\log n)$，细节较为繁琐。

参考代码。