Triplet Min Sum | CS Academy #30 (Div. 2 only)

実は解候補はlca(A,B), lca(B,C), lca(C, A)の3通りしかない。

与えられた木を根付き木とし、簡単のため

depth(A) <= depth(B) <= depth(C)

とする。Aを考慮しなければ、下のような図が描ける。

(1)Aがパス(B,C)上にある場合

明らかにAが解になる。

A=lca(A,B)またはA=lca(A,C)

(2)Aがパス(B,C)上にない場合

Aは上図の囲われていない部分のいずれかにある。Aパス(B,C)上にないので、Aからパス(B,C)に到達するのに必ず通らなければならないある(B,C)上のある1点が存在する。この点は

lca(A,B)またはlca(B,C)またはlca(C,A)

である。