LCA
Lowest Common Ancestor…最小共通祖先の問題のこと。
https://gyazo.com/b368660349c45ee8c36a579134f8a428
このように、グラフ上の点が2点与えられた時に、一番近い共通の祖先を返す、というのがLCAの問題だったりします。
普通にLCAを求めるプログラムを書いてみると、
２点からいい感じに親を辿っていって、親が一緒だったときそれを返す
みたいなのになるので、木の深さくらいの計算量がかかったりかからなかったりします。
なので色んな人が色んな時短法を編み出してきました。
ダブリング
普通の実装でやろうとすると、上に辿っていくパートで深さの回数だけループを回す必要が出てきます。
なので、最初の時点で
自分の1つ上にある頂点
自分の2つ上にある頂点
自分の4つ上にある頂点
…
自分の$ 2^nつ上にある頂点
をそれぞれの頂点について計算しておけば、上に辿っていく時爆速で辿れませんか？というアイデアです。
実装