解答:Submission #10579618 - AtCoder Grand Contest 033
解法:木の直径に注目すると、直径の端点を選んだ場合は直径が1減少し、それ以外の点を選んだ場合は直径が2減少する。
よってこのゲームは「木の直径から1または2を交互に減少させてゆき、木の直径を1にすると負け」というゲームに帰着される。
このゲームは木の直径を3で割った時のあまりが1なら後手の勝ちで、それ以外は先手の勝ちである。
- 木の直径を3で割った時のあまりが0:先手があまり2をキープし、直径が2になった時に先手が端点を選ぶ
- あまりが1:後手があまり2をキープし、直径が2になった時に後手が端点を選ぶ
- あまりが2:先手があまり0をキープし、直径が3になった時に先手が端点を選ぶ