Green Hackenbush
最近看到一个有意思的博弈问题。
对于一张无向连通图（不一定是简单图），规定一个点为根，两个玩家轮流操作，每次可以删掉根可以到达的一条边，不能操作者输。
这类博弈即 Green Hackenbush 。
树
从简单情况入手，对一棵有根树做 Green Hackenbush ，如何得到一棵树的 SG 值？
首先，如果树的点数恰为 1 ，SG 值显然为 0 。
如果根的度数恰为 1 ，设与根相连的点为 \(u\) ，设 \(u\) 的子树对应的 SG 值为 \(k\) ，不难发现原树的 SG 值即 \(k+1\) 。
如果根的度数大于 1 ，那么可以把根“分裂”，把原树拆成一个森林，每个森林的根的度数都恰好为 1 。容易发现这个森林与原树等价，那么应用 SG 定理，原树的 SG 值就是每个子树的 SG 值加一的异或和。
图
对于一般图的情况如何处理？
有一个定理，把图缩成边双树，然后对于一个有 \(k\) 条边的边双，在对应节点上挂 \(k\) 个点（其实也可以挂 \(k \bmod 2\) 个点），这样得到的一棵树的 SG 值与原图相同。
证明
这篇博客写得好水啊，补个证明算了。
融合
等价于把所有形如 \((y, z)\) 的边替换为 \((x, z)\) 然后删去点 \(y\) ，然后如果 \(y\) 是根，把根换成 \(x\) 。
这样的操作称为在图中融合两个点 \(x, y\) 。
引理 1
对于一张只有恰好一个点数至少为 2 的环且该环包含根的图，融合该环上任意两点，游戏的值不变。
证明
咕咕咕。
定理 1
对于仙人掌图，融合同一环上的任意两点，游戏的值不变。
证明
考虑边双树，从叶子开始逐个考虑，对于一个点数至少为 2 的环，考虑其子树，根据引理 1 该环上任意两点是可以融合的。把该环上所有点融合继续归纳，可以证明所有环都是可以把任意两点融合的。
定理 2
对于任意图，融合同一边双联通分量上的任意两点，游戏的值不变。
证明
证明一个等价的命题，任意图一定满足两个条件之一：
- 没有边双联通分量
- 存在一对在同一个边双联通分量的点，融合后游戏的值不变。
（只要证明存在性是因为，如果一个点对是不满足定理的，那么融合其他点后该点对始终不会满足定理，因此只要把满足定理的点对不断融合即可）
对图的边数应用数学归纳。边数为 \(0\) 的时候显然满足条件 1 。假设边数不超过 \(n\) 时都成立，考虑一个边数为 \(n+1\) 的图。分类讨论。
情况 1
没有边双联通分量，满足条件 1 。
情况 2
存在两个点 \(x, y\) ，它们之间有至少三条边不重复的路径。
这时候融合 \(x, y\) ，游戏的值是一定不变的。设原图为 \(G\) ，融合后的图为 \(H\) ，考虑游戏 \(G + H\) 。先手进行一次操作后，后手在另一张图上进行同样的操作，注意到一次操作至少删掉一条边，因此双方操作后两张图的边数都不超过 \(n\) 。这个时候可以把两个图不断进行融合，可以发现融合后两张图完全一致，因此 \(G + H\) 是一个值为 \(0\) 的游戏，这意味着 \(G\) 和 \(H\) 相等，融合不影响游戏的值，满足条件 2 。
需要注意的是，由于 \(x, y\) 之间有至少三条边不重复的路径，在双方操作后 \(x, y\) 之间有至少两条边不重复的路径，因此总是可以融合的。
情况 3
如果图既不满足情况 1 也不情况 2 ，这样的图一定是仙人掌图。应用定理 1 即可，满足条件 2 。
参考文献
论文有点看吐了，咕咕咕的地方到时候再补吧。