No.039 D

二重辺連結成分分解をして, 連結成分を縮約したグラフを作成する. このグラフは木になる.

縮約した頂点で $A-B-C$ がトレイルになるためには, $D(A, B) + D(B, C) = D(A, C)$ となればいい. ただし $D(x, y)$ は $x, y$ 間の距離である.

$D(x, y)$ は $x, y$ のLCAを $z$ として, $E(x) + E(y) - 2E(z)$ で求められる. ただし $E(x)$ は $x$ の木の深さである.