博弈论，以及处理树上邻域的技巧，感觉有点套路。
首先容易发现一个点 $x$ 的 SG 函数是其子树的最大深度 $d_x$，并且对于每个棋子都是一个独立的游戏，那么总的 SG 函数就是所有子游戏的异或和 $c_x=\oplus[a_i\equiv 1\pmod 2] f_i$（以 $x$ 为根）。于是得到放一个棋子的充要条件 $\max_i d_i<c_x$。
考虑在 $x$ 上放一个棋子产生的影响。设 $y$ 为 $x$ 的长儿子，即 $x$ 最大深度的链经过 $y$。那么对于子树 $y$ 内的所有节点的 $c_i$ 需要异或上 $x$ 经过其他儿子的最大深度；对于其他子树内的所有节点，需要异或上 $d_x$。对于这个操作我们容易用树状数组实现。
考虑查询，关键之处在于查询范围是一个邻域。这意味着我们还需要维护儿子 的信息。考虑直接建 Trie 树，将每个子节点加进去。