题解：CF1585G Poachers

Grisses · 2025-01-02 22:07:00 · 题解

考虑对每棵树算 sg 值，容易发现有 \begin{cases}dp_{x,0}&=&\operatorname{mex}\limits_{i=1}^{lim_x}dp_{x,i}&\\dp_{x,i}&=&\bigoplus\limits_{v}dp_v{i-1}&(i>0)\end{cases}。

其中 dp_{x,i} 表示以 x 子树中距 x 距离为 i 的所有点为根的子树的 sg 的异或和，lim_x 表示 x 子树中离 x 最近的叶子的距离。

考虑先给所有叶子挂一个虚点，这样就避免了特判一步删空。

发现这玩意和深度有关，于是我们可以得到一个基于长剖的线性做法。

• 如果 x 是叶子，sg_x=dp_{x,0}=0。
• 如果 x 只有一个儿子 v，考虑其所有后代的 sg 值组成的集合 S_x，可以发现有 S_x=S_v\cup\{sg_v\}。同时有 sg_x=\operatorname{mex}S_x，发现 sg_x 可以从 sg_v 暴力往上枚举，对于一整条长链，最多跳 \Theta(len) 次。
• 如果 x 有多个儿子，考虑将所有 dp_{x,i} 求出后直接暴力算出 sg_x，复杂度 \Theta(lim_x)。

也就是说我们总的复杂度为所有长链的长度之和，即 n。

代码。