Description:
あるTreeの全ての葉の間の距離が与えられた時、Treeの枝の長さの総和の求めよ
Treeの葉の数は30以下で、葉と葉の間の距離は100以下。
Answer:
葉Aから葉Bに行く時のPathと、葉Aから葉Cに行く時のPathの共通部分の長さは、(A-B間の長さ + A-C間の長さ - B-C間の長さ)/2で求めることが出来る。
Cに全ての葉を当てはめ、最小値をとる事により、葉Aから最も近い節点までの距離を求めることが出来る。
ここで、葉Aと、葉Aから最も近い節点までの枝を取り除くことによって、葉の数が1つ少ない
これを木が2点を残した棒状になるまで繰り返す。
答えは、取り除いた枝の長さの総和+最後に残った棒の長さになる。
計算オーダーはO(n^2)
共通部分の枝の長さは半整数になる所だけ注意が必要。
Source: