デンソークリエイトプログラミングコンテスト2022 (ABC239) F - Construct Highway (500)
$ \sum_i D_i \ne 2n - 2の場合、そもそも木にならないので達成不可能
$ m個のクエリでそれぞれの点をUnionFind上でマージし、それぞれの$ d_iを1引く
$ m個の既存の高速道路を引いた時点で$ d_i \lt 0な点がある場合、達成不可能
それぞれの連結成分毎に残っている辺の受け口を配列に入れる
それぞれの$ iで$ d_i回ずつ$ iを追加する
連結成分間の結合は残り1以上のと2以上との間で行う
1同士をくっつけるとそれ以上結合できなくなってしまうため
連結成分を持っているDの和の降順にソートする
先頭の連結成分に対して後ろの連結成分をどんどんマージしていく
最終的に全ての要素が連結になっていればOK