原案者です。原案時点での想定解が準備者の想定解と違うことをやっていそうなので簡単に説明します。

既約分数 \(a/b\) が与えられたときに、Stern-Brocot Tree の根から \(a/b\) までのパスを、辺を左の子へ向かうものか右の子へ向かうものかでラベル付けしてランレングス圧縮(RLE)した列を高速に求める方法を考えます。

• 例： \(a/b=3/8\) のとき、根から頂点 \(3/8\) には 左, 左, 右, 左 と進めば辿り着けるので (左, 2), (右, 1), (左, 1) が求めたいものです。

状態を行列で表現してみましょう。

\(a/b\) に対応する状態 \(S(a,b)\) を、\((a,b)\) を右・左で挟む分数の分子・分母をそれぞれ 1 行目と 2 行目に書いた行列とします。例えば \(S(3, 8)\) の場合、\(3/8\) は \(1/3\) と \(2/5\) に挟まれているので

\[ S(3, 8) = \left( \begin{array}{cc} 2 & 1 \\ 5 & 3 \end{array} \right) \]

です。また、根に対応する行列 \(S(1,1)\) は

\[ S(1,1) = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) = I \]

、すなわち単位行列です。左右に潜る行列 \(L, R\) も定義できて(\(L, R\) は右から作用する)、これは

\[ L = \left( \begin{array}{cc} 1 & 0 \\ 1 & 1 \end{array} \right), R= \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array} \right) \]

です。(\(L = S(1, 1)L = S(1, 2), R = S(1, 1)R = S(2, 1)\) なのを考えると明らかです。)よって、例えば次の式が成り立ちます。

\[S(3, 8) = L^2 R L\]

さて、逆向きの操作を考えてみましょう。\(L, R\) の逆行列を \(L' = L^{-1}, R' = R^{-1}\) とします。つまり

\[ L'= \left( \begin{array}{cc} 1 & 0 \\ -1 & 1 \end{array} \right), R'= \left( \begin{array}{cc} 1 & -1 \\ 0 & 1 \end{array} \right) \]

です。

\[S(a, b) = M_1 M_2 \dots M_k\]

としたとき、\(S(a,b)\) に \(M_1^{-1}\) を左から作用させて、\(M_2^{-1}\) を左から作用させて、…を繰り返せば初期状態 \(S(1, 1) = I\) に戻ることができます。例えば \( L' R' L' L' S(3, 8) = S(1, 1) = I\) です。

また、詳細は略しますが、根 \(a=b=1\) を除くと \(L' S(a, b)\) と \(R' S(a, b)\) のうち 係数が すべて非負であるものはちょうど一方のみであることが証明できます。そして、\(S(a,b)\) と \(L'(a,b), R'(a,b)\) の関係を詳しく考察すると次の事実が分かります。

• \(a \lt b\) の場合は \(L' S(a, b) = S(a, b - a)\) が成り立つ。
• \(a \gt b\) の場合は \(R' S(a, b) = S(a - b, b)\) が成り立つ。

ここで行列の話はまどろっこしいので取っ払ってしまいましょう。\(P(a/b)\) を 辺を \(L, R\) でラベル付けした根から \(a/b\) までのパスとします。(例：\(P(3/8) = (L, L, R, L)\)) すると上の事実は次のように言い換えられます。

• \(a = b = 1\) の場合 \(P(a/b) = \phi\)
• \(a \lt b\) の場合 \(P(a / b) = (L) + P(a / (b - a))\)
• \(a \gt b\) の場合 \(P(a / b) = (R) + P((a - b) / b)\)

よってこの問題は \((a, b)\) を \(a,b\) の大小に応じて \((a, b-a)\) または \((a-b,b)\) に移す問題に言い換えられて、これは互除法の典型言い換えです。よって、詳細は略しますが、これを上手く使えば \(a/b\) の パスの RLE が \(\mathrm{O}(\log (a+b))\) で求まるとわかります。

ここからは雑談です。RLE の数字部分を取り出した列を \(A = (A_1, A_2, \dots, A_k)\) とすると(ただし パスの先頭のラベルが \(L\) の場合は \(A\) の先頭に \(0\) を追加する) 、次の式が成り立ちます。

\[\frac{a}{b} = A_1 + \dfrac{1}{A_2 + \dfrac{1}{\ddots + \dfrac{1}{A_k + 1}} }\]

たとえば \(3/8\) については \(A = (0, 2, 1, 1)\) で

\[\frac{3}{8} = 0 + \dfrac{1}{2 + \dfrac{1}{1 + \dfrac{1}{1 + 1}} }\]

です。よって、以上の導出は、Wikipedia 等に載っている連分数展開を陽に利用した解法とおおむね似たようなことをやっていそうです。(連分数展開は苦手なのでちゃんと理解していませんが…)

また、このように逆行列を掛けながらお絵かきをしていると、根から \(a/b\) のパスが \(\mathrm{rev}(P(a/b))\) になるある種の双対的な木が構成できるな？という気持ちになると思うんですが、そのような木には Calkin-Wilf Tree という名前がついているようです。(最近 Twitter で流れてきて知りました。Project Euler を埋めている人には有名らしいです。) 使い道は何も知らないんですが面白そうですね。

さて、本題に戻ります。以上の問題が解ければ、 \(a/b\) と \(c/d\) の LCA を \(\mathrm{O}(\log(a+b+c+d))\) で計算できるので、与えられた頂点集合に対する Virtual Tree(Auxiliary Tree, 指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木) を\(\mathrm{O}(N \log N \log A)\) で構成することができます。(Suffix Array などのデータ構造を用いれば \(\mathrm{O}(N \log A)\) 程度に計算量を落とせそうな気もします。) そして、木上のマージテクの要領で頂点集合をマージしながら適宜求めたい値を計算していけばよく、この部分は std::set を利用すれば \(\mathrm{O}(N \log^2 N)\) で計算できます。よって全体で \(\mathrm{O}(N \log N (\log N + \log A))\) でこの問題を解くことができます。