解説スライドではオイラーツアーを用いた解法が省略されているということですが、こちらではオイラーツアーを用いた \(75\) 点 ( \(L_2=54\) ) の解法を紹介します。

便宜上、数列は左から右に並んでいるとします。

適当に根を取って長さ \(19998\) のオイラーツアー（辺列）をとり、これに沿って進んだ時に至る深さの列 \(D\) （長さ \(19999\) ）を求めます。各頂点の ID は対応する \(D\) の（最小の）添え字にします。 \(D\) の隣接する要素の間の差は \(\pm1\) ですから、 \(D\) 内の変化の様子はビット列でやり取りできます。

\(D\) を長さ \(B=14\) のブロック \(1429\) 個に切り分けると、解説スライドの方法で \(X,Y\) が含まれる \(2\) つのブロックの番号を順不同で Ali が知ることができます。

\(X\) , \(Y\) が同じブロックに含まれる場合は、長さ \(B-1\) のビット列でブロック内の \(D\) の変化の様子を伝えればよいです。

そうでない場合、 \(X \lt Y\) とし、 \(X\) が含まれるブロックを \(b_X\) 、 \(Y\) が含まれるブロックを \(b_Y\) と表します。

例えば Benjamin に次の情報がすべて伝わればよいです。

1. \(D\) で、 \(b_X\) の右端から \(b_Y\) の左端まで（ \(b_X\) , \(b_Y\) からそれぞれ端の \(1\) 要素を含む）の最小値
2. \(b_X\) の右端の値
3. \(b_Y\) の左端の値
4. \(b_X\) 内の変化の様子
5. \(b_Y\) 内の変化の様子

Benjamin は \(X\) 、 \(Y\) 、 \(X\) と \(Y\) の lowest common ancestor 、の \(3\) 点の深さを求められるので、 \(X\) , \(Y\) 間の距離が求まります。

1,2,3 は位置関係でよいので、次のように削減されます。

1. \(b_X\) の右端から \(b_Y\) の左端までの最小値 を \(k\) とする。（この値は不要）
2. \(b_X\) の右端の値から \(k\) を引いた値 \(Q_2\)
3. \(b_Y\) の左端の値から \(k\) を引いた値 \(Q_3\)
4. \(b_X\) 内の変化の様子 \(Q_4\)
5. \(b_Y\) 内の変化の様子 \(Q_5\)

\(Q_2\) , \(Q_3\) の値は \(0\) 以上 \(10000\) 以下より、 \(14\) ビットです。 \(Q_4\) , \(Q_5\) はそれぞれ長さ \(B-1=13\) のビット列です。

よって、 \(L_2=14+14+13+13=54\) で問題を解けました。