P8994 [北大集训 2021] 经典游戏

考试题目。

考虑用 $S G$ 函数解决问题，那么 $S G (x) = \oplus_{y \in subtree(x), y \neq x} S G (y)$ ，叶节点 $S G (x) = 0$ 。容易发现 $S G (x) = d_{x}$ ，其中 $d_{x}$ 为 $x$ 为根的子树的最深深度。我们只处理 $a_{i} \equiv 1 (\mod 2)$ 的 $S G (x)$ 值。那么先手必胜的充要条件即 $\oplus_{a_{x} \equiv (\mod 2) 1} S G (x) > d_{y}$ 。

考虑我们需要进行的操作，换根， $a_{x} \oplus 1$ ，以及求满足 $d i s (y^{'}, y) \leq 1$ 的 $y^{'}$ 。s

不妨设点 $1$ 为初始根。考虑换根操作， $d e p_{x}$ 只与 $f a_{x}$ 有关。于是 $S G$ 值发生改变的只有以 $1$ 为根 $1 \to x$ 链上节点，这一部分不会因为 $a_{x} \oplus 1$ 而改变。我们可以简单树形 DP 得到。我们还需要异或上以 $x$ 为根 $x \to 1$ 的。

考虑 $a_{x} \oplus 1$ 。而 $x$ 对点 $x^{'}$ 产生影响的条件是 $x \in subtree (x^{'})$ ，并且子树 $x$ 为子树 $x^{'}$ 中最深的子树，即为 $x$ 的长儿子。于是我们直接长链剖分，那么修改是长链上开头的连续一段，树状数组维护。