Codeforces Round #668 (Div. 2) D. Tree Tag
気づき
- Aliceが一回の移動で木の全部に移動できるなら必勝
- 1.でないとき、Bobがaliceの2倍より大きく動けるなら必勝
1.については、は具体的にいくつか書いてみれば気づくと思う。
問題は、一回で全域をカバーできる移動距離の最小値を求めることで、その方法に気づけるかがポイント。
知っていればなんということもないが、具体的にそこそこ複雑な木を書いてみると、なんとなく木の中心っぽいところから始めようとか、一番長い端の点から端の点の真ん中からの距離が必要ということがわかると思う。
あとは検索力を発揮して、「木の中心」「木 最遠」あたりで検索すれば、「木の半径（直径）」という概念にたどり着くと思われる。
結局、が木の半径以上なら（木の中心に移動してから）一手で全部の頂点をカバーできるので、Aliceの必勝となる。
（木の半径（または直径）の求め方は割愛）
次に2.についてだが、単純な例を考えてみれば気づくと思われる。
fig.1のような状態を考えると、が
の倍より大きければ、千日手となって、Bobの必勝となる。
注意しないといけないのは、条件1.の場合は問答無用でAliceの必勝なので、条件の優先順位に気をつけて実装する必要がある。
また、一手目でAliceがBobを捕まえられる場合に注意。
