「取り除いた辺の長さの合計を最大にする」ということは、「取り除かなかった部分の長さの合計を最小にする」ことと同じです。
取り除かなかった部分は木になるため、これは最小全域木を求める問題になり、元のグラフの辺の合計 - 最小全域木の辺の合計が答えになります。
