Least Common Ancestor O(d) time and O(1) space

木の頂点 $u$, $v$ について最小共通先祖 (LCA) を計算するシンプルなアルゴリズムを紹介します．複数の頂点の組に対して LCA を求めるのであれば，木を前処理をしてクエリあたり $O(\log n)$ なり $O(1)$ で求めるのが定石ですが，ここではそうでなく，線形時間かけて求めることを考えます．木は親ポインタ parent: &[Option<usize>] によって与えられるとします．

O(n) 時間 O(n) 空間アルゴリズム

すぐに思いつくアルゴリズムは頂点に訪問済みかどうかをあらわすフラグをもたせて各頂点から親方向に走査するものでしょう．このアルゴリズムは領域の確保に $O(n)$ 時間かかる上に $O(n)$ 空間を消費するので非効率的です．

fn lca(parent: &[Option<usize>], u: usize, v: usize) -> usize {
    let mut x = u;
    let mut y = v;
    
    let mut seen = vec![false; parent.len()];
    loop {
        seen[x] = true;
        if let Some(p) = parent[x] {
            x = p;
        } else {
            break;
        }
    }
    loop {
        if seen[y] {
            return y;
        }
        if let Some(p) = parent[y] {
            y = p;
        } else {
            unreachable!();
        }
    }
}

O(d) 時間 O(1) アルゴリズム ver 1

別のアルゴリズムとして $O(d)$ 時間かけて $u$ と $v$ の深さを求め，深い方だけを親方向に走査して深さを揃えてから同時に親に進んでいくものがあります．このアルゴリズムは全体で $O(d)$ 時間 $O(1)$ 空間を達成するので最適です．

fn depth(parent: &[Option<usize>], u: usize) -> usize {
    let mut x = u;
    for d in 0.. {
        if let Some(p) = parent[x] {
            x = p;
        } else {
            return d;
        }
    }
    unreachable!()
}

fn lca(parent: &[Option<usize>], u: usize, v: usize) -> usize {
    let mut x = u;
    let mut y = v;

    let d_x = depth(parent, x);
    let d_y = depth(parent, y);
    for _ in d_y..d_x {
        x = parent[x].unwrap();
    }
    for _ in d_x..d_y {
        y = parent[y].unwrap();
    }
    while x != y {
        x = parent[x].unwrap();
        y = parent[y].unwrap();
    }
    x
}

O(d) 時間 O(1) 空間アルゴリズム ver 2

上述のアルゴリズムは最適ですが，こんな簡単な手続きのためにこんなコード量を使いたくないところです．そこで以下では別の最適なアルゴリズムを紹介します．

fn lca(parent: &[Option<usize>], u: usize, v: usize) -> usize {
    let mut x = u;
    let mut y = v;
    while x != y {
        x = parent[x].unwrap_or(v);
        y = parent[y].unwrap_or(u);
    }
    x
}

このアルゴリズムでは，変数 $x$ は頂点 $u$ から親方向に進み，根に到達したら頂点 $v$ に戻って同じ手続きを繰り返します．最初に根に至るまでを１巡目，次に根に至るまでを２巡目と呼ぶことにします．変数 $y$ は頂点 $v$ から同様の手続きを行います．以下このアルゴリズムが LCA を求めることを証明します．

$a$ を $u$ と $v$ の LCA とします．もし $u$ と $v$ の深さが等しければ１巡目の走査によって $a$ が発見されます．$u$ と $v$ の深さが異なるとしましょう．このとき変数 $x$ が頂点 $a$ に到達するステップ数は となります．同様に変数 $y$ が頂点 $a$ に到達するステップ数は となります．これらは等しいのでそれぞれ２巡目の走査で $a$ が発見されます．