D - Shortest Paths on Unicyclic Graph

この問題は、グラフを閉路と木に分解することで解くことができます。

この問題で与えられるグラフは、閉路からいくつかの木が生えている形になっています。ここでは、閉路のそれぞれの頂点も木と考えます。

この問題での $2$ 頂点間の最短路は、次の $2$ パターンが考えられます。

• $2$ 頂点が同じ木に属している場合
• $2$ 頂点が異なる木に属している場合

$2$ 頂点が同じ木に属している場合

この場合は、木上の最短路を計算すればよいです。

木上の最短路は、前処理 $O(N)$ 、クエリ $O(\log N)$ 程度で効率的に求めることができます。

無向木では、最短路について次のような性質が成り立ちます。

• 頂点 $u, v$ 間の最短路を $d(u, v)$ と表す。また、ある頂点 $r$ を根としたとき、頂点 $u, v$ の最小共通祖先を $\text{LCA}(u, v)$ とする。
• $d(u, v) = d(r, u) + d(r, v) - 2d(r, \text{LCA}(u, v))$

つまり、 $2$ 頂点間の最短距離は根からの最短距離と最小共通祖先を使って表すことができます。

ここで根からの最短距離は DFS によって $O(N)$ で求まり、最小共通祖先も前処理 $O(N)$ 、クエリ $O(\log N)$ 程度で行うアルゴリズムが知られています。

根とするのはどの頂点でも問題ないですが、閉路に含まれる頂点を根とすると次のクエリが計算しやすいです。

$2$ 頂点が異なる木に属している場合

答えは、それぞれの頂点の閉路までの距離と閉路での距離の和になります。

それぞれの頂点の閉路までの距離は DFS をすることで前処理 $O(N)$ 、クエリ $O(1)$ で求まります。

また、閉路での距離は累積和によって前処理 $O(N)$ 、クエリ $O(1)$ で求まります。

よって、この問題は $O(N + Q \log N)$ で解くことができました。