人権なし

競プロで解いた問題や開発の進捗などの記録です

AtCoder Beginner Contest 148:F - Playing Tag on Tree

問題

https://atcoder.jp/contests/abc148/tasks/abc148_f

解法

高橋君は木のどこかの葉に逃げるのが適切なので,それぞれの葉に逃げたときの青木君の移動回数を求め,それらの max を答えとすればよい.

まず,ある葉(頂点 t)までの距離 dist_ut と dist_vt が dist_ut >= dist_vt のとき,高橋君は葉 t に到達する前に青木君につかまってしまう.このときの青木君の移動回数は dist_uv / 2 回.

一方,dist_ut < dist_vt のとき,高橋君は葉 t に到達することが出来る.その後は葉 t の一歩手前の頂点 t' と t をうろつくのが良い.ここで dist_uv がいかなる場合も高橋君は頂点 t' でつかまることが分かる.よって,青木君の移動回数は dist_vt - 1.

頂点間の距離の取得は LCA 木を前計算で準備しておくと O(logN) で可能.全体で O(NlogN).

解答

https://atcoder.jp/contests/abc148/submissions/9080471

f:id:babcs2035:20191222224006p:plain