二人旅

閉路がなく任意の都市へ行き来できることからうしたぷにきあ王国は木として処理することができます。 都市$Z$から各都市への最短距離を求めた後、二人旅の最大値を求めるために$Z$を根とした最近共通祖先(LCA)を調べます。 クエリ$(A_i,B_i)$のLCAが都市$C_i$だったとき$Z$から$C_i$への最短距離が答えになります。 したがって、計算量は $O((v+e)\log v + q \log q)$ です。