ABC014 D - 閉路

D - 閉路
提出コード
初めてLCAを扱う問題に触れました。
現在の木の根を適当に決めます。どこでもいいです。
新しく追加する辺の2つの頂点の番号をa,bとします。このとき、閉路の長さは、

• (aの根からの深さ)+(bの根からの深さ)-2×(aとbの共通の祖先で最も近い頂点の、根からの深さ)

となっています。
なので、それぞれの深さ、およびLCAを求めれば、比較的簡単に答えを求めることができます。