LCA: Lowest Common Ancestor

• 最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ #AtCoder - Qiita
  • LCA はオイラーツアー & Range Minimum Query （Segtree など）で解ける
  • ダブリングでも解ける（けど定数倍が遅い？）

LCA でできること

• 木での全頂点対最短経路問題
  • 普通のグラフではワーシャルフロイド法で求めてたもの。
  • tbw: 計算量は？
• 木で、点 a がパス u-v にあるかの判定