A 大きい頂点から貪欲に取れば良い事に気づけばおしまいB 辺を、最大全域木だけで考えてもOKな事に気づけばおしまいD SegTreeでとても単純にやればおしまい 少なくともO(Nlog^3 N)だけど、O(Nlog^2 N)で押さえられる気もする