はじめに
おはようございます。所で、lca-based auxiliary tree の頂点の個数は 2|X| - 1 以下という表式を持ちます参考。本記事ではそれを示すにあたって重要な役割を果たす定理を、細かい命題を積み上げることで示す事を目指します。最初に、この記事は自己満足の色が濃い事を断っておきます
定理
示すstatementはこれです。
根付き木 $T$ について、行きがけ順が $i, j, k (i < j < k)$ である頂点 $v_i, v_j, v_k$ を取った時、$lca(v_i, v_k)$ は $lca(v_i, v_j)$ と $lca(v_j, v_k)$ のうち少なくとも1方と等しい。
尚これからは頂点集合を $V$ で表します。また、 $lca$ や 行きがけ順、先祖と部分木の定義は既知とし、$v \in V$ の行きがけ順を $pre(v)$ で表します。
命題1
$\forall v \in V$, 集合 $\{pre(x) \mid xはvの部分木に含まれる\}$ は区間である
行きがけ順を求めるアルゴリズムが、$v$ に一度入った後 $v$ の部分木内の頂点全てを訪れてから $v$ から出ていく事を言えば良いです。高さについての帰納法を考えると示せます。
この命題より、 $v \in V$ に対し自然に区間が対応します。この部分木の行きがけ順の区間を $I_v$ で表すことにします。
系1
$a, v \in V$ に対し、 $v$ が $a$ の部分木に含まれる ⇔ $pre(v) \in I_a$
ほとんど定義。
系2
$a, v \in V$ に対し、 $a$ が $v$ の先祖 ⇔ $pre(v) \in I_a$
先祖と部分木の関係から明らか。
$I_v$ の交差や包含の関係について、その定義より部分木と殆ど同様に扱える事がわかります。具体的には次の2つの命題の成立が言えます。
命題2
$u, v \in V, (u \neq v)$ について、 $u, v$ の高さが同じ $\Rightarrow$ $I_u$ と $I_v$ は共通部分を持たない
命題3
$v \in V$ と、その親 $p \in V$ について、 $I_v \subset I_p$
系3
$u, v \in V, (u \neq v)$ とある $h$ に対し、$(\exists v_h \ s.t. v_h の高さは \ h \ かつ\ \{pre(u), pre(v)\} \in I_{v_h}) \Rightarrow (\forall h' \le h, \exists v_{h'} \ s.t. v_{h'} の高さは \ h'\ かつ\ \{pre(u), pre(v)\} \in I_{v_{h'}})$
1度 $\{pre(u), pre(v)\} \in I_{v}$ となったら、命題3よりその先祖の $I$ は全て $\{pre(u), pre(v)\}$ を含むことより成立。
木の各高さ $h$ に対して $\{I\}_h := \{I_v \mid vの高さがh\}$ を考えます。ここで命題2より、それぞれの $h$ について $pre(u) \in I$ となる $I$ が存在するならばそれは一意です。
ここで、系3と同値な以下の命題が得られます。
$u, v \in V, (u \neq v), \ \exists h_{uv} \ s.t. \ (h \le h_{uv} ⇔ \exists! \ I \in \{I\}_h \ s.t. \ \{pre(v_i), pre(v_j)\} \subset I)$
注意: これは $(u, v)$ の2ペアにとどまらず、 $(u, v, l)$ 等3タプルでも成立します（一般に頂点の集合なら成立します）
$I_v$ と $lca$ に関して次が成立します。
命題4
$u, v \in V, (u \neq v)$ について、 $lca (u, v)$ は、 $u$ の先祖である頂点 $l$ であって、 $\{pre(u), pre(v)\} \subset I_l$ となる $l$ の内最も低い位置にある頂点である
系2と $lca$ の定義から明らか。
定理の証明
statementの再掲
根付き木 $T$ について、行きがけ順が $i, j, k (i < j < k)$ である頂点 $v_i, v_j, v_k$ を取った時、$lca(v_i, v_k)$ は $lca(v_i, v_j)$ と $lca(v_j, v_k)$ のうち少なくとも1方と等しい。
$v_i, v_j$ のペアに対し、系3の2つ目の命題が存在を保証する値 $h$ を $h_{ij}$ と置きます。および、$v_j, v_k$ のペアに対応する値を $h_{jk}$と置き、 $v_i, v_k$ に対応する値を $h_{ik}$と、 $v_i, v_j, v_k$ のタプルに対応する値を $h_{ijk}$ と置きます。
$h_{ij}$ と $h_{jk}$ の大小関係で場合分けします。
h_{ij} <= h_{jk} の時
命題1より以下が成立します。
$$ h_{ij} = h_{ik} = h_{ijk}$$
そして命題4より $lca(v_i, v_k)$ と $lca(v_i, v_j)$ はそれぞれ $h = h_{ik}, \ h_{ij}$ の時の定義中の $\exists ! I$ を持つ頂点であり、これらは共に $h = h_{ijk}$ の時の定義中の $\exists ! I$ を持つ頂点 でもあるので
$$lca(v_i, v_k) = lca(v_i, v_j)$$
が成立します。
h_{jk} <= h_{ij} の時
先ほどと同様にして
$$ h_{jk} = h_{ik} = h_{ijk}$$
$$lca(v_i, v_k) = lca(v_j, v_k) $$
よって場合分けが尽くされ、定理は示されました。
あとがき
お疲れ様でした。いかがでしたか? 大学の数学の入門教材のような、細かい命題が全体を構成していて、1つ1つの証明をそこまで頑張らないような証明が書いてみたくて本記事を書いてみました。
個人的には少し回りくどい議論になってしまった気もしています。特に最初の方の $I_v$ の定義パートを書いている時には虚無感すら感じました。最後に $I_v$ の区間性を用いた事でトントンといった具合です。
部分木の包含関係を区間の包含関係に落とすとわかり易くて頭に優しいです。色々書いただけあって、読むのにあまり無理のない構成にはできたと思っています。特に、1つ1つの殆ど成立が明らかな命題を（必要ならば証明も添えて）納得していくことで、自然と全体が自明に感じて頂けたら幸いです。