適当に根を決めて BFS 木を作って LCA を求める部分は公式解説と同じです． BFS 木に含まれない辺 \(e = \{u, w\}\) を使う場合は，明らかに頂点 \(u\) と頂点 \(w\) を経由します． したがって，頂点 \(s\) から頂点 \(t\) への辺 \(e\) を経由する最短路の長さは，同頂点間の頂点 \(u\) を経由する最短路の長さを超えません． 頂点 \(u\) から各頂点 \(v\) への距離を \(\mathrm{dist}(u, v)\) とすると，後者は \(\mathrm{dist}(u, s) + \mathrm{dist}(u, t)\) と計算できます．

以上より，BFS 木に含まれない各辺 \(e = \{u, w\}\) に関して，一方の端点 \(u\) を選んで \(\mathrm{dist}(u, v)\) の値をあらかじめ計算しておけば，各クエリでは BFS 木での LCA から求めた値と上記の値の最小値を求めればよいです． \(\mathrm{dist}(u, v)\) の計算は \(d = M - N + 1\) 本の辺に関して一方の端点を選んで BFS すればよいので，LCA の計算量に加えて，事前計算に \(\mathrm{O}(dM)\) 時間，クエリに合計 \(\mathrm{O}(dQ)\) 時間かけることでこの問題が解けました．