srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

LCA

ABC 014 D - 閉路

問題 問題概要 木のグラフが与えられる。その木に対して、辺を1つ加えでできる、閉路の長さを答える。 解法 まず、LCAを求める。LCAについては、蟻本。多くのクエリが与えられるので、いちいち親をたどっていては、間に合わない。そこで、頂点vから、2k回上…