No.048 D

木を根付き木と考え, 頂点 $i$ の深さを $D(i)$, 頂点 $i, j$ の LCA を $L_{ij}$ とする.

たこ焼き屋に寄らないときの所要時間は,

$$T = 2(D(s)+D(t)-2D(L_{st}))$$

である.

たこ焼き屋に寄る場合は, $s - t$ の経路上のどこかの点 $u$ から一番近いたこ焼き屋に寄って, 再度 $u$ に戻ることになる. $u$ から一番近いたこ焼き屋までの距離を $E(u)$ とする.

所要時間は $u$ が $s - L_{st}$ 上にあるときは,

$$\begin{align} T &= 2(D(s)-D(u))+3E(u)+(D(u)+D(t)-2D(L_{st})) \\ &= 2D(s)+D(t)-2D(L_{st})+3E(u)-D(u) \end{align}$$

となり, $u$ が $L_{st} - t$ 上にあるときは,

$$\begin{align} T &= 2(D(s)+D(u)-2D(L_{st}))+3E(u)+(D(t)-D(u)) \\ &= 2D(s)+D(t)-4D(L_{st})+3E(u)+D(u) \end{align}$$

となる.

$E(u)$ はすべてのたこ焼き屋をキューに入れて幅優先探索をすれば求められる.

$3E(u) \pm D(u)$ をすべてあらかじめ計算しておき, $u$ から $2^k$ 個上までの頂点までの最小値をダブリングの要領で計算しておけば, $3E(u) \pm D(u)$ は $O(\log N)$ で求めることができる.