根の深さを \(0\) として、深さが偶数の頂点に石を置くと最終的に自分の色に、奇数の頂点に石を置くと相手の色になります。 したがって、Alice 、Bob が手順中に石を置くことになる「深さが奇数の頂点」の個数をそれぞれ \(a,b\) とすると、Alice の得点は \((N+1)/2-a+b\) であり、Alice は \(a\) 、Bob は \(b\) を最小化すればよいと分かります。

この後、深さが偶数の頂点を赤、奇数の頂点を青の頂点とします。

ここで、木を次のような規則でいくつかのグループに分解します。

1. 葉となっている赤頂点があれば、それは独立した1つのグループとする。
2. 既にグループに分けられている頂点を除いた部分木のうち、親の子が \(1\) つではない青頂点に着目し、 そのうち最も部分木のサイズが小さい頂点の部分木をグループとする。
3. 上記を、全ての頂点がグループに属するまで繰り返す。ただし、根の親として仮想的な青頂点を \(1\) つ付加して考えておく。

このとき、各グループに属する青頂点の数を「コスト」と呼びます。 各グループは、全て奇数個の頂点を持つこと、 グループ内で順に頂点を取っていくと青→赤→青…となる（赤単体からなるグループを除く）ことから、 このゲームは「コストの決まったグループを順に選び、そのコストを支払って相手に手番を渡す」というゲームと解釈できます。

ここで、実際には木の中で頂点が選ばれる順番によって、 グループの分割が先に述べたものから変化することがありますが、そのような選択をしても得をしないことが示せます（後述）。 また、元のゲームとの整合性を考えると、グループの選ばれる順は、 各グループとなった部分木の根が子孫側にある方から順に選ばれている必要がありますが、 グループ分けの規則より、子孫側の部分木からなるグループは祖先側のグループより必ずコストが小さいため、 コストが小さい方から選ばれている限りは木上のゲームの手順に矛盾なく対応することが保証されます。

したがって、上記のように計算したグループのコストを、小さい方から交互に取っていく進行がお互いの最善手であり、 このときのコストの総和がそれぞれが手順中に石を置く青頂点の個数になります。

【上記手順が最善であることの証明】

各時点の木の状態に対して、上記のグループ分けの規則にしたがって分解したとき、 「その時点でコストが最小であるグループから一つ、取れる頂点を取る」（条件Ⓐとします） ことが最善であることを示します。

すると、結果として、与えられた木をグループに分解し、コストの小さい方から順に、 そのグループ内の頂点が尽きるまで交互に頂点を取っていく、という先に述べた進行になります。

手順の最後から、数学的帰納法で示します。

まず、残りの頂点がパス状になった時、唯一の可能な手は条件Ⓐを満たしています。

次に、頂点を選択可能で、最後に条件Ⓐに違反した手が選択された手番を考えます。 便宜上、このときに手番を持っているプレイヤーを先手と呼びます。

この時点で実際に取られた頂点が属するグループのコストを \(k\) とします。 また、残っている他のグループのコストを小さい方から \(a,b,c,...\) とします。 この際のゲームの進行は、

①\(k>1\) のとき

先手がコスト \(k\) のグループからコスト \(1\) を切り出して先に取り、 結果としてコスト \(0\) と \(k-1\) のグループが生まれた、と解釈できます。 したがって、その後の進行は（先手のこの手も含めて）

• \(1 → 0 → a → b → c → k-1 → ... \)

となります。一方、先手が条件Ⓐを満たす手を指していた場合

• \(a → b → c → k → ...\)

となります。 後手が払うコストは、元の進行において \(k\) のグループを先手が取っていた場合 \(\pm 0\)、 後手がとっていた場合 \(-1\) となり、いずれも先手の得ではありません。

② \(k=1\) のとき

このとき、他にコスト \(0\) のグループが存在します。よって、\(a=0\) とします。この際の進行は

• \(k=1 → a=0 → b → c →... \)

となります。一方、先手が条件Ⓐを満たす手を指していた場合

• \(a=0 → k=1 → b → c →... \)

となっていたはずです（ \(b=0\) や \(c=0\) の場合は \(k\) の登場が遅くなります）。 この場合も、後手が払うコストの増減は \(\pm 0\) または \(-1\) であり、先手の得ではありません。

したがって、この場面において先手は条件Ⓐを満たす手を指すのが最善であったと分かります。

この議論を初手まで遡ることにより、解説に記した手順が最善です。