F. Astra
一道博弈论好题，重点在于本题考察 SG 函数的方式不是常见的打表猜结论，而是结合了记忆化搜索，感觉非常新颖。
读题后可以发现这是一个公平组合游戏，可以利用 SG 函数求解每个状态的 SG 值。每次操作涂色的点一定是一条自上而下的链，且链头必须与某个已涂色点相邻。从中我们很容易发现，每次涂色会将某一棵完全未涂色的子树分割成多棵完全未涂色的子树，每棵子树可以看作是一个状态，而不同子树的操作显然是相互独立的，根据 SG 函数的性质，这些子树的 SG 值异或和即为当前涂完某条链后的 SG 值。
一个朴素想法是：对于每个 \(s \in [1, n]\)，求解该情况下的 \(n\) 棵子树的 SG 值，这样的状态数是 \(O(n^{2})\) 的；而求解每个状态的 SG 值需要枚举所有后继状态（枚举从根出发的所有长度 \(\le k\) 的路径）的 SG 值并求它们的 mex ，复杂度 \(O(n)\)，总复杂度 \(O(n^{3})\)。
但事实上，这里有很多状态是重复的，去重后的状态数是 \(O(n)\) 的：考虑树的每条有向边 \((u, v)\) 指向的子树，该状态可以看作 \(u\) 已涂色，对以 \(v\) 为根的子树进行操作，总共有 \(2n\) 条有向边。
由于总状态数 \(O(n)\)，暴力求解每个状态的复杂度为 \(O(n)\)，且状态之间具有递推关系，因此不难想到使用记忆化搜索来优化求解，总复杂度 \(O(n^{2})\)。具体实现见 code。
code