No.067 D

木構造になっているので, まずはお互いに $1$ と $N$ を結ぶルート上のマスを確保するのが最適である. そうすると, そのマスから分岐している部分木上のマスはすべて自分しか塗れなくなるからである.

よって, $1$ と $N$ を結ぶルート上のマスを塗りきったときにお互いが確保している部分木にある町の数を数えて比較して, 多い方が勝ちとなる. 部分木にある町の数が同じならば, 手番の人が負けである.

まずは $1$ を根とする木を作成する. そうすれば $N$ から親をたどっていけば $1$ から $N$ のルートを作成できる.

次に葉から順に部分木の町の数を数える. $1$ から $N$ のルート上の町はそれ以降の計算を行わない. こうして $1$ から $N$ のルート上の町から分岐している部分木にある町の数が計算できる.