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