「AGC017D」题解 _lbw_ · 2023-03-24 22:38:53 · 题解 怎么都没有一点解释的，看不起 SG 函数？？ 我们发现这题是一个 DAG 博弈论问题，考虑 SG 函数。 我们设 u 子树博弈后的 SG 函数为 f_u，u 子树的 DAG 为 g_u。 考虑对于 u 计算 f_u。 对于每个 v,s.t\ \exists(u,v)，都看作是一个子 DAG，同时我们每时每刻都可以直接把 (u,v) 这条边割掉，于是新建一个节点，将 g_v 中的每一个节点都连向 0 得到 g'_v，于是 g'_v 里的每个点 SG 值应当都加上 1，于是 g'_v 的 SG 值 f'_v=f_v+1 。 我们知道很多 DAG 拼一起 SG 值是它们的异或和，于是 f_u=\oplus_{(u,v)=1}(f_v+1)。 做完了。