木のu-vパスでuからv側にひとつ動いた頂点を求めるクエリ

このクエリをverifyできるAOJ/yukicoderの問題を探しています

アルゴリズム

まずは $O(N\log N)$ の前計算で level ancestor を $O(1)$ で求められるようにしておきます

${\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}}_u\ge {\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}}_v$ のとき、求める頂点は ${\mathrm{p}\mathrm{a}\mathrm{r}}_u$ です

${\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}}_u<{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}}_v$ のとき、$l=\mathrm{l}\mathrm{a}(v,{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}}_v-{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}}_u-1)$ として、求める頂点は ${\mathrm{p}\mathrm{a}\mathrm{r}}_l=u$ なら $l$、そうでなければ ${\mathrm{p}\mathrm{a}\mathrm{r}}_u$ です

クエリ当たりの計算量は $O(1)$ です

実装例

next beet-aizu.github.io

問題例

codeforces.com