题解 ABC239F【Construct Highway】

翻译：给定 \(n,m\) 和度数数组 \(\{d_i\}\)，再给你 \(m\) 条边，请构造一棵 \(n\) 点的树包含这 \(m\) 条边，且第 \(i\) 个点的度数为 \(d_i\)，或者判断无解。

显然，若 \(\sum d_i\ne 2(n-1)\)，则无解。

然后对于输入的每条边，使用并查集维护，再求出在这 \(m\) 条边的基础上每个点还需要多少度数（记作 \(d_i\)，注意下文 \(d_i\) 的意义与输入不同）。

如果存在 \(d_i < 0\)，则无解。

然后考虑每个连通块，维护一个 vector 表示这个连通块中每个点还需要多少度数，若 \(u\) 需要 \(k\) 的度数就存 \(k\) 个 \(u\)。

将所有连通块分为两类：需要度数 \(1\)、需要度数 \(\ge 2\)，下文分别称为“第一类”“第二类”。

第一类连通块显然要优先跟第二类连通块连（不然就不连通了）。我们枚举每个第二类连通块，假设这个连通块还需要 \(d\) 的度数，那么拿出 \(d-1\) 的度数连第一类连通块，剩下 \(1\) 的度数会使得这个连通块被归入第一类中。

如果某一时刻第一类连通块不够了，就无解。如果所有第二类连通块都用完了，此时剩下超过 \(2\) 个第一类连通块，就也无解。否则，此时会恰好剩下两个第一类连通块，连起来即可。最后判一下整个图是否连通，不连通还无解。否则输出即可。

这题无解情况挺多的，容易漏情况，写代码之前要想清楚。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const int N = 2e5+5;

int n, m, deg[N];
vector<int> nds[N], nd1;
vector<vector<int>> nd2;
vector<tuple<int, int>> ans;

struct Dsu {
    int fa[N];
    void init(int x) {rep(i, 1, x) fa[i] = i;}
    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    bool same(int x, int y) {return find(x) == find(y);}
    bool merge(int x, int y) {
        if(same(x, y)) return false;
        x = find(x); y = find(y);
        fa[x] = y;
        return true;
    }
}dsu;

int main() {
    scanf("%d%d", &n, &m);
    rep(i, 1, n) scanf("%d", &deg[i]);
    if(accumulate(deg+1, deg+1+n, 0) != 2 * (n - 1)) return puts("-1")&0;
    dsu.init(n);
    rep(i, 1, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        dsu.merge(u, v);
        --deg[u]; --deg[v];
        if(deg[u] < 0 || deg[v] < 0) return puts("-1")&0;
    }
    rep(i, 1, n) rep(j, 1, deg[i]) nds[dsu.find(i)].push_back(i);
    rep(i, 1, n) {
        if((int)nds[i].size() == 1) nd1.push_back(nds[i][0]);
        if((int)nds[i].size() > 1) nd2.push_back(nds[i]);
    }
    for(auto&& i : nd2) {
        for(int j = 1; j < (int)i.size(); j++) {
            if(nd1.empty()) return puts("-1")&0;
            dsu.merge(i[j], nd1.back());
            ans.emplace_back(i[j], nd1.back());
            nd1.pop_back();
        }
        nd1.push_back(i[0]);
    }
    if((int)nd1.size() > 2) return puts("-1")&0;
    dsu.merge(nd1[0], nd1[1]);
    ans.emplace_back(nd1[0], nd1[1]);
    rep(i, 1, n) if(!dsu.same(i, 1)) return puts("-1")&0;
    for(auto&& [u, v] : ans) printf("%d %d\n", u, v);
    return 0;
}