疑問
https://atcoder.jp/contests/abc014/tasks/abc014_4
この問題を解いていて、根を頂点1にするとACできたのですが、なぜこれでACできたのかと疑問に思いました。根の頂点をnなど他の頂点にしてもACできていて、なぜだろうと疑問に思って謎がわかったので記事にします。
根が変わるとどうなるのか
ペイントで描いてみました。aとbに対して新しく辺を結ぶとして、根を2パターン書いて、その場合のaとbの最小共通祖先と、その最小共通祖先との距離を書いています。
見てみると、根が変わると最小共通祖先の頂点は変わってしまいますが、aと最小共通祖先の距離、bと最小共通祖先の距離、この二つの和はどちらも同じであることがわかります。また、当然なことではありますが、根が変わってもaとbの二頂点間の距離も変わりません。
まとめ
変わるもの →根と最小共通祖先の頂点
変わらないもの →最小共通祖先と二頂点との距離を和。二頂点の距離
主客店頭みたいなイメージをするなら、「二頂点間のパスで通るどこか一頂点を最小共通祖先とする」みたいな感じになるかもしれません。
おわりに
上級者の方には当然なことかもしれませんが、LCAを初めて勉強していて疑問に思ったことを記事にしてみました。ここまで見ていただきありがとうございます。