以下では、\(d(u, v)\) で頂点 \(u, v\) の最短距離を表します。

まず、全ての頂点を一度ずつ通る場合を考えます。\(u\) から出発して \(v\) で移動を終了するとき、\(u, v\) を結ぶ最短パスに含まれる辺は \(1\) 回以上、そうでない辺は \(2\) 回以上通らなければなりません。よって総移動距離は \(2(N - 1) - d(u, v)\) 以上になりますが、実際にこの下界を達成することができます。以下に移動方法の概略を示します。

• \(u\) を根とする深さ優先探索を行う。
• 頂点 \(v\) へ向かう辺は最後に探索することにする。
• 頂点 \(v\) を根とする部分木に含まれる頂点を全て通り終えたら、移動を終了する。

上記の方法は、辺の重みが \(1\) とは限らない一般の非負整数であるとしても最適解を与えます。

通らなければならない頂点 \(A_1, \dots, A_K\) が与えられたとき、これらの頂点に対応する Virtual Tree（Reduced Tree や Auxiliary Tree とも呼ばれる）の辺の重みの総和と直径が分かればクエリに答えることができます。適当な根をとったときのオイラーツアー順で \(A_1, \dots, A_K\) を並び替えると、\(d(A_1, A_2) + d(A_2 + A_3) + \dots + d(A_{N - 1}, A_N) + d(A_N, A_1)\) は辺の重みの総和の二倍に等しくなります。また、直径は以下のアルゴリズムで計算することができます。

• \(A_1\) から最も遠い頂点を \(A_k\) とする。
• \(A_k\) から最も遠い頂点までの距離が直径である。

\(d(u, v)\) は LCA などを計算することで \(O(\log N)\) 程度で計算できます。よって、一つのクエリあたり \(O(K \log N)\) 程度の計算量で解くことができました。