ABC148 F - Playing Tag on Tree

問題原文

atcoder.jp

問題要旨

木の上で高橋くんと青木くんが鬼ごっこをする。高橋くんは逃げる側、青木くんは逃げる側。
高橋くんから、「相手と同じ頂点にいたらゲーム終了。そうでなければ１手移動。」を繰り返す。
高橋くんは出来るだけ捕まらないように、青木くんは出来るだけ早く捕まえられるように行動する時、青木くんは何回移動することになるか？

考えるべきこと

高橋くんは、「高橋くんが捕まらずにたどり着ける頂点のうち、青木くんから最も遠いもの」を目指せば良い

視点を高橋くんから青木くんに持っていけばわかる。
高橋くんから最も遠い頂点が、青木くんにとって最も遠い頂点でないことに注意。 視点が高橋くんのままだと詰まるりそう。

ある頂点を経由して、高橋くんにとっての理想の頂点を目指す時、途中で捕まらないか？

ある頂点 が存在して、 高橋くんのいる頂点を ,　青木くんがいる頂点を とするとき、 ならば、頂点 からさらに潜る？頂点たちへは、高橋くんの方が必ず早くたどり着けるから大丈夫。

最後に青木くんが追いついて終了？高橋くんが青木くんに向かって行って終了？

落ち着いて図を書けば、実はどちらのターンで終わるかは関係ないことがわかる。

高橋くんが向かって行って終了のパターン

青木くんが追いついて終了のパターン

共通しているのは、「高橋くんが追いつかれるのは行き止まりに追い詰められた時」で、「捕まる場所は葉の親」だということ。

結局

頂点 と 頂点 それぞれについて、 全頂点への距離を計算し、 を満たすようなもののうち、最大の が答えになる。

実装

N, u, v = map(int, input().split())
u, v = u - 1, v - 1
T = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append([b, 1])
    T[b].append([a, 1])

# 最短距離が求められればなんでもいい
U_dist = dijkstra(T, u)
V_dist = dijkstra(T, v)
 
ans_candidates = [dv for du, dv in zip(U_dist, V_dist) if du < dv]
print(max(ans_candidates) - 1)

学び

• 一人のプレイヤーの視点にこだわりすぎないようにしよう
• 落ち着いて図を書こう

類題さん。。。。
atcoder.jp