一度ある部分木にコマが置かれると、その部分木からコインが無くなるまではコマが部分木の外に出ることはありません。 また、一度部分木の外にコマが出たあとは、二度とその部分木にコマが置かれることはありません。 よって、部分木ごとに再帰的に問題を解いていくことができます。

\(f(v)\) を「 \(v\) の部分木でこのゲームをしたときに、先手が獲得するコインの枚数と後手が獲得するコインの枚数の差」として、 \(f(v)\) を木の構造について再帰的に計算していきます。

最適な行動

\(v\) の部分木でゲームをしたとき、まず先手が頂点 \(v\) に置かれたコイン \(1\) 枚を入手します。 その後、後手がどの頂点にコマを動かすかを選ぶことになります。このときの最適な選び方について考えるために、 頂点 \(v\) の子であるような頂点 \(u\) に対して、以下の \(3\) 通りの場合分けをします。

1. \(f(u)\lt 0\) かつ \(u\) の部分木のサイズが偶数
2. \(f(u)\ge 0\) かつ \(u\) の部分木のサイズが偶数
3. \(u\) の部分木のサイズが奇数

1 の頂点にコマを動かしたとき、動かした人が（その部分木内で）相手よりも多くコインを獲得できる上に、その後でもう一度 \(v\) の子の頂点を選ぶことができます。 このような頂点にコマを動かして得することはあっても、損することは無いため、1 の頂点があるときは必ずそこにコマを動かすのが最適です。

2 の頂点にコマを動かしたとき、相手よりもコインを多く獲得することはありません。さらに、その後にもう一度 \(v\) の子の頂点を選ぶことになります。 つまり、この頂点を選んでも選ばなくても手番に影響は無いにもかかわらず、決して得をすることは無いため、この頂点を積極的に選ぶ理由はありません。 よって、2 の頂点はなるべく選ばない（最後に選ぶ）のが最適です。

3 の頂点にコマを動かしたときは、その部分木のコインがすべて取られたあと、自分で \(v\) にコマを戻すことになります。よって、 3 の頂点を選んだ場合、次に \(v\) の子の頂点を選ぶのは相手であるため、今すぐに一番「良い」部分木を選ばないと相手に取られてしまいます。 よって、子の頂点に 3 の頂点が存在していた場合、そのうち \(f(u)\) の最も小さいものに動かすのが最適です。 その結果、3 の頂点が複数個存在していた場合、 \(f(u)\) の小さい順に 後手、先手、後手、… と交互に動かしていくことになります。

この最適な行動をもとにして \(f(v)\) を計算すると、この問題を解くことができます。 3 の頂点の処理をするときにソートをする必要があるため、計算量は \(O(n \log n)\) となります。

C++による実装例

Pythonによる実装例