JOI春合宿2007 Salt
これだけはテストできないので、思いついた解法を書きます。
解法
木に対して「辺を取り除く」「頂点とそれにつながる辺を取り除く」という操作は、元の木を分解していくつかの新しい木を生み出す操作である。よって、木の Grundy 数を求めればよい。
N >= 1 のとき、頂点数 N の木の Grundy 数が、N が奇数のとき 1 、N が偶数のとき 2 であることを帰納的に示す。
i. N = 1 のとき
頂点は 1 個しかない。それを取り除くと、一切の頂点がない状態になる。この状態の Grundy 数は 0 である（遷移不能）。よって、N=1の場合の Grundy 数は 1 である。
ii. N = k+1 かつ、N が偶数のとき
ある辺を取り去った場合、残る 2 つの木の頂点数は、「どちらも奇数」もしくは「どちらも偶数」になる。仮定より、頂点数が奇数、偶数のときの Grundy 数はそれぞれ 1, 2 であるから、2 つの木の Grundy 数の XOR を求めると 0 になる。
ある頂点を取り去った場合、残る頂点数は奇数になる。この場合、奇数個の頂点からなる木が奇数個と、偶数個の頂点からなる木が偶数個になるので、同様にして Grundy 数は 1 になる。
以上より、N が偶数の場合の Grundy 数は 2 である。
iii. N = k+1 >= 2 かつ、N が奇数のとき
ある辺を取り去った場合、残る 2 つの木の頂点数は、片方が奇数で片方が偶数になる。よって、この場合の Grundy 数は 3 になる。
ある頂点を取り去った場合、残る頂点数は偶数なので、奇数個の頂点からなる木が偶数個と偶数個の頂点いくつかに分かれる。ここで、偶数個の頂点が奇数個存在する場合は Grundy 数が 2 、偶数個存在する場合は Grundy 数が 0 になる。
一方、最初の木について、すべての頂点の次数（その頂点から出る辺の数）の合計は偶数である。頂点数が奇数であることより、少なくとも 1 つの頂点が存在し、次数は偶数である。そのような頂点を選んで取り去ると、Grundy 数は 0 になる。
以上より、N が奇数の場合の Grundy 数は 1 である。
i, ii, iii より示された。
