E - Swap on the tree

キーワード

最短経路問題

解説

初期状態では各頂点にただ $1$ つの置物が置かれており，操作では $2$ つの頂点に置かれている置物を入れ替えるので，操作を何回行っても各頂点にただ $1$ つの置物が置かれていることは保たれます。
したがって，各頂点にただ $1$ つの置物が置かれている状態のみを考えます。

$i=1,2,...,N$ について頂点 $i$ に置物 $g_i$ が置かれている状態は，$i$ 文字目を $g_i$ とした文字列で表現することができます。
例えば，$N=8$ の場合で文字列 34567812 は，頂点 $1$ に置物 3 ，頂点 $2$ に置物 4 ，...，頂点 $8$ に置物 2 が置かれている状態を表現しています。
このような文字列 $S$ は，$1$ から $N$ までの数字の並べ方の数だけあり，全部で $N!$ 通りあります。
また，入れ替えを行う操作は状態遷移であり，頂点 $i$ とその親 $\lfloor \frac{i}{2} \rfloor$ の置物を入れ替える操作は，$S$ の $i$ 文字目と $\lfloor \frac{i}{2} \rfloor$ 文字目の数字を入れ替えてできる文字列を $S'$ としたときの，$S$ から $S'$ への遷移に対応します。
よって，$N!$ 通りの文字列 $S$ を頂点とし，$1$ 回の操作で遷移が可能な任意の $2$ つの文字列 $S,S'$ に対し無向辺を張ったグラフを考えたとき，この問題は，数列 $A$ で定められる状態 $P$ から数列 $B$ で定められる状態 $Q$ までの最短経路問題に帰着することができます。

頂点の数を $V$ ，辺の数を $E$ とすると計算量は幅優先探索なら $O(V+E)$ ，ダイクストラ法なら $O(E \log V)$ です。
問題の制約より $V \leq 40320，E \leq 141120$ なのでどちらのアルゴリズムでも十分高速です。
各頂点の始点からの距離を記録するには連想配列を用いると実装しやすいです。

実装例(C++)

類題