考试题目。
考虑用 $SG$ 函数解决问题，那么 $SG(x)=\oplus_{y\in \text{subtree(x)},y\neq x} SG(y)$，叶节点 $SG(x)=0$。容易发现 $SG(x)=d_x$，其中 $d_x$ 为 $x$ 为根的子树的最深深度。我们只处理 $a_i\equiv 1 \pmod 2$ 的 $SG(x)$ 值。那么先手必胜的充要条件即 $\oplus_{a_x\equiv \pmod 21} SG(x)>d_y$。
考虑我们需要进行的操作，换根，$a_x \oplus 1$，以及求满足 $dis(y’,y)\le 1$ 的 $y’$。s
不妨设点 $1$ 为初始根。考虑换根操作，$dep_x$ 只与 $fa_x$ 有关。于是 $SG$ 值发生改变的只有以 $1$ 为根 $1\to x$ 链上节点，这一部分不会因为 $a_x\oplus 1$ 而改变。我们可以简单树形 DP 得到。我们还需要异或上以 $x$ 为根 $x\to 1$ 的。
考虑 $a_x\oplus 1$。而 $x$ 对点 $x’$ 产生影响的条件是 $x\in \text{subtree}(x’)$ ，并且子树 $x$ 为子树 $x’$ 中最深的子树，即为 $x$ 的长儿子。于是我们直接长链剖分，那么修改是长链上开头的连续一段，树状数组维护。