以下の補題が成り立ちます。

補題

\(S_{j}=T_{i}\) かつ \(T_{j}=S_{i}\) のとき、クエリ \(i,j\) の答えはどちらも等しい。

証明は省略します。

ヒントとしては背理法を用いて、答えが違うと仮定し、蘇生のタイミングの位置から矛盾を示すことで証明ができます。

以降、Pakenomy 社 の構造を部屋 \(1\) を根とした辺重みつき根付き木とします。

上の補題から、各クエリごとに以下が分かれば答えを求めることができます。

• \(L_{i}:=S_{i},T_{i}\) の LCA(最小共通祖先)
• \((countX_{i},endX_{i}):=S_{i}\rightarrow L_{i}\) に向かう途中に蘇生される回数(\(L_{i}\) に到着するタイミングも含む)と最後に蘇生されたときにいる頂点
• \((countY_{i},endY_{i}):=T_{i}\rightarrow L_{i}\) に向かう途中に蘇生される回数(\(L_{i}\) に到着するタイミングも含む)と最後に蘇生されたときにいる頂点
• \(dist_{i}:=endX_{i}\) と \(endY_{i}\) の距離

上記がわかっているとき、 \(dist_{i}<K\) なら \(ans_{i}=countX_{i}+countY_{i}\)、そうでないなら \(ans_{i}=countX_{i}+countY_{i}+1\) となります。

これらを各クエリごとに高速に求められればいいです。

ダブリングで解く方法を解説します。

まず以下の配列を作ります。

\(pare[i][j]:=\) 頂点 \(i\) から根の方向に \(2^{j}\) 回進んだときにたどり着く頂点(存在しないときは \(-1\) 等)

\(j\) は \(O(\log(N))\) 程度まで求められればいいです。

\(pare[i][0]\) は BFS 等などで \(O(N)\) で求まり、 \(pare[i][j+1]=pare[pare[i][j]][j]\) が成り立つことからこの配列は \(O(N\log(N))\) で求められます。

頂点 \(i,j\) のLCAを求める関数

LCA や最小共通祖先等で検索すれば配列 \(pare\) を使って求める方法が出てくると思います。この後出てくる関数もほとんどこの原理を用いています。

計算量は \(O(\log(N))\) です。

頂点 \(i\) から \(k\) 回根に向かって進んだときにいる頂点とその距離を求める関数

前述した配列を使って bit ごとに見ればよいです。

クエリごとの計算量は \(O(\log(N))\) です。

頂点 \(i\) から 根に向かって進んだときに \(k\) 回目の蘇生のときにいる頂点を求める関数

\(reborn[i][j]:=\) 頂点 \(i\) から根の方向に 進んでいる途中に \(2^{j}\) 回蘇生されたときにいる頂点(存在しないときは \(-1\) 等)

とする配列が組めればクエリごとに \(O(\log(N))\) で求められます。

この配列は \(reborn[i][0]\) を配列 \(pare\) を用いて \(i\) ごとに \(O(\log(N))\)求めることで \(O(N\log(N))\) で求めることができます。

クエリごとの計算量は \(O(\log(N))\) です。

以上を組み合わせれば答えを求めることができます。

例えば、 \(dist_{i}\) は頂点の深さと LCA が分かれば「頂点 \(i\) から \(k\) 回根に向かって進んだときにいる頂点とその距離を求める関数」を用いて求められます。

全体の計算量は \(O((N+Q)\log(N))\) です。

実装例 C++