No.014 D

木は頂点 $1$ を根とする根付き木とする.

入力があった $a, b$ の LCA $c$ を求める. LCA の求め方はいろいろあるが, ここでは HL 分解法を使っている.

頂点 $x$ の深さを $D(x)$ とすると, $a, b$ をつなげたときの閉路の長さは $(D(a) - D(c)) + (D(b) - D(c)) + 1$ となる.