二部グラフについて

奇閉路を持たないグラフのことを二部グラフといいます。これは次と同値です

• 同じ色の頂点を結ぶ辺が存在しないように、頂点を \(2\) 色に塗り分けることができる

このとき、同じ色で塗られた頂点をそれぞれ集めることで、頂点全体を 2 つに分けることができます。これを部集合といいます。
連結な二部グラフに対する部集合の定め方は一意であり、適当な頂点から始めて BFS や DFS などをすることで求めることができます。

問題の解法

木は二部グラフです。2つの部集合のサイズを \(A,B\) とすると、二部性を保ったまま追加できる辺の個数は \(AB-(N-1)\) です。これらをどのような順序で追加しても、ある辺が追加可能であるかどうかには影響しません。よって、元のゲームは「\(AB-(N-1)\) 個の選択肢から交互に1個ずつ選んでいき、選べなくなったほうが負け」となります。これは \(AB-(N-1)\) が奇数なら先手必勝、偶数なら後手必勝です。
予めDFSなどによりグラフの各頂点が2つの部集合のどちらに属するかを求め、追加可能な辺の選択肢を全て列挙してsetなどで保持しておくことでこの問題を解くことができます。