D: Game on Tree - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

木の根を含まない部分木を交互に取り除いていき、操作ができなくなった(根しかない状態になった)ほうが負けとする。最適な行動を取る時先手後手どちらが勝つか？

Green Hackenbushとかいう有名問題とのこと。明らかにGrundy数であるが、導出はやや複雑。結果だけ書くとある部分木について、その部分木のGrundy数をすべてxorを取り、1を足すことで元の部分木のGrundy数になる。これを再帰的に計算し、Grundy数が0ならば後手の勝ちで、そうでなければ先手の勝ちである。O(N)。