最近共通祖先
最小共通祖先とかLowest Common Ancestor(LCA)とか言われるやつ
問題
頂点$ 1 を根とする木で、ノード$ i, j から辿って最初に合流するノードはどこか？
解法
ざっくり2つ
ダブリング
各ノードの$ 1, 2, 4, ... 個上のノードを記録しておいて、二分探索的に求める方法。前計算$ O(N \log N) 、クエリ$ O(\log N )
オイラーツアー
木をDFSしつつノードを記録した配列を作り、その配列を使って区間クエリに答える系の技を使って答える方法。
DFS部分で$ O(N) 、その後データ構造によって変わるが前計算$ O(N \log N) クエリ$ O(1) が可能。
応用
2点間のキョリ
頂点$ 1 からノード$ n のキョリを$ d(n) として求めておく。
ノード$ i, j のLCAが$ k のとき、$ i \rightarrow j の最短ルートは$ i \rightarrow k \rightarrow j 。
$ k が$ i,j の祖先なので、$ i \rightarrow k のキョリは$ d(i)-d(k) 、$ j \rightarrow k のキョリは$ d(j)-d(k) となって、$ i \rightarrow j のキョリは$ d(i) + d(j) - 2d(k) となる。
参考
（"頂点"と"ノード"両方使ってるけど、この2つ同じ意味なのでは？）