LCA (Lowest Common Ancestor; 最近共通祖先) がバグっていた

ダブリングで LCA を求めるスニペットがバグっていました。Library Checker で AC したので大丈夫かと思っていたのです。

バグに気づけなかった理由は木の入力形式だとわかりました。

復習です。

ダブリングにより根付き木の LCA を求めるアルゴリズムでは、前計算として、木の各頂点 $v$ と $i = 0, 1, 2, \dots$ について

$f(i, v)$: 頂点 $v$ から根方向に $2^i$ 回辺を辿った頂点

を求めます。たとえば $f(0, v)$ は $v$ の親です。*1

さて、$v$ から根へ $2^i$ 回辺を辿ることは「$v$ から $2^{i - 1}$ 回辺を辿った頂点 = $f(i - 1, v)$ から $2^{i - 1}$ 回辺を辿ること」と同じです。したがって漸化式は次のようになります。

$$ f(i, v) := f(i - 1, f(i - 1, v)) $$

$f(i, v)$ を求めるには、たとえばボトムアップ的に $(i, v)$ の昇順に計算すればよいです。

for (int i = 1; i < lg; i++) {
    for (int j = 0; j < n; j++) {
        anc[i][j] = (anc[i - 1][j] == -1) ? -1 : anc[i - 1][anc[i - 1][j]];
    }
}

このように実装すれば、$f(i, v)$ を求める際に $f(i - 1, \ast)$ が確定しているため、$f(i - 1, f(i - 1, v))$ が正しく計算されます。

Library Checker の LCA https://judge.yosupo.jp/problem/lca では木が次の形式で与えられます。

N
p[1] p[2] ... p[N-1]

p[i] は頂点 $i$ の親を表し 0 <= p[i] < i を満たします。

このとき、$(v, i)$ の昇順に $f(i, v)$ が計算できてしまいます。実際、頂点 $v$ の祖先はすべて $v$ 未満なので $f(i - 1, v) < v$ より $f(i - 1, f(i - 1, v))$ が正しく計算されます。

したがって外側のループと内側のループを入れ替えても正しく動きます。(提出)

for (int j = 0; j < n; j++) {
    for (int i = 1; i < lg; i++) {
        anc[i][j] = (anc[i - 1][j] == -1) ? -1 : anc[i - 1][anc[i - 1][j]];
    }
}

もちろん、木が次の形式で与えられる場合はうまくいきません。たとえばこの問題です。

N
a[1] b[1]
a[2] b[2]
︙
a[N-1] b[N-1]

*1:$i$ が大きい場合は根を飛び越してしまうので、そのような場合は実装上 $f(i, v) = -1$ や $f(i, v) = \infty$ とすればよいです。

1日9時間寝たい