簡単のため、連結グラフが与えられるとします。また、本問題と同値な操作後の次数が奇数の頂点に書かれた整数の値の最小化を考えます。

次数の総和は偶数であるため、次数が奇数である頂点の個数は偶数である必要があります。これは実は十分条件でもあります。次数が奇数である頂点の個数が偶数個である状態を全て構築可能であることを証明します。

全ての辺を削除する状態にします。次に、次数を奇数にしたい頂点 \(2\) 個からなる組\((u,v)\) を作ります。全ての組に対して、グラフ上での \(u-v\) パスを \(1\) 個取り、そのパス上の辺の削除するかどうかの状態を切り替えればよいです。

よって、\(A\) をソートした後に小さい方から偶数個選ぶ方法を全て試せばよいです。

以上より、本問題を \(\mathrm{O}(N\log N)\) で解くことができます。