Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【蟻本】オイラーツアーとRMQを組み合わせてLCAを実装する

今日はオイラーツアーの日と決めたので、オイラーツアーの理解を深めるために、オイラーツアーとRMQの組み合わせでLCA(Lowest Common Ancestor)を実装するという蟻本に書いてあるネタをまとめておきます。

この部分は一度読んだ時に、IQが低すぎてあまり理解出来なかった記憶があり、同様にIQが低い人の役には立つと思います。

f:id:akiradeveloper529:20191006145727j:plain

左のグラフの中でLCAを求めたいです。

ここでおもむろに行きがけ帰りがけでオイラーツアーをして、深さも記録しておきます。(深さはオイラーツアー中に計算する必要はなく、別途でいいです)

こうすると何が良いかというと、この表の中でuとvを適当に選べば、その間にあるもっとも深さが小さいものがLCAということです。

数列に対して、「もっとも小さいもののインデックスを求めよ」は、Sparse Tableを使うと出来ます。(Sparse TableとLCAはともにダブリングが基本的なアイデアです)

www.rustforbeginners.com

例えば、LCA(4,5)を求めてみます。この時、どれでもよいですが、vが4と5のものを選びます。蟻本では最初にvが現れるところを使うということになっていますが、その限りではないです。

適当に、赤丸で囲った4と5をとってみます。これはグラフ上、赤線で示したパスに相当します。こうしても、LCA(4,5)=2が求まります。