ABC148 F. Playing Tag on Tree
問題
N頂点の木が与えられる。
最初、高橋くんは頂点u、青木くんは頂点vにいる。
2人は以下の手順で鬼ごっこをする。
- 高橋くんと青木くんが同じ位置にいるなら終了。そうでないなら、高橋くんは隣接頂点のどれかに移動
- 高橋くんと青木くんが同じ位置にいるなら終了。そうでないなら、青木くんは隣接頂点のどれかに移動
- 上記を繰り返す
高橋くんはできるだけ長く、青木くんはできるだけ速く終了するように行動する。
高橋くんと青木くんが最適に動いた場合、ゲームが終了するまでに行動した青木くんの移動回数を答えよ。
制約
- 2 <= N <= 10^5
- 1 <= u, v <= N
- u != v
解法
まず、青木くんの最初にいる頂点vをルートとして各頂点への最短移動をdfsなどで求める。
高橋くんは、各頂点へはこの青木くんの距離よりも短い距離で移動できる場合、自由に移動できる。
なので、高橋くんも同様に頂点uをルートとして各頂点への最短距離を求める。ただし、青木くんの最短距離以下の場合のみ移動できる。
青木くんの最短距離と高橋くんのその頂点への移動距離が等しい場合は、高橋くんから青木くんにぶつかりにいって終わるパターン(サンプル3)なので、答えとしてはあり得るので、それ以上の移動はないが、答えには含めて考えておく。
そうでない場合は、最後の状態に注目すると、高橋くんのターンでは、
-
-
-
- [ 青木くん ] ---- [ 高橋くん ]
-
-
のような場合か
-
-
-
- [ 青木くん ] ---- [ ] ---- [ 高橋くん ]
-
-
のようになっている。
どちらの場合でも、高橋くんがいる頂点の一つ前の地点で終了するので、高橋くんが移動できる範囲で、「青木くんが一番遠くに移動する距離から1引いたところ」が終了状態になるので、これを答えれば良い。
