C++(clang++ 11.0.1) 解法, 执行用时: 56ms, 内存消耗: 5736K, 提交时间: 2022-09-06 10:27:55

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, m, ka, kb;
int f[N], d[N], p[N], a[N], b[N];

void tree2prufer()
{
    for (int i = 0; i < ka; i ++ )
    {
        scanf("%d", &a[i]);
        d[a[i]] ++ ;
    }
    for (int i = ka; i < m - 1; i ++ ) {a[i] = 1;d[a[i]] ++ ;}
    for (int i = 0; i < kb; i ++ )
    {
        scanf("%d", &b[i]);
        d[b[i]] ++ ;
    }
    for (int i = kb; i < n - 1; i ++ ) {b[i] = n + m;d[b[i]] ++ ;}
    for (int x = 0, y = 0, j = 1; x + y <= n + m - 2 ; j ++ )
    {
        while (d[j]) j ++ ;
        if(j >= n + 1) p[x + y] = a[x], x ++;
        else p[x + y] = b[y], y ++;
        while (x + y <= n + m - 2 && -- d[p[x + y - 1]] == 0 && p[x + y - 1] < j) {
            if(p[x + y - 1] >= n + 1) p[x + y] = a[x], x ++;
            else p[x + y] = b[y], y ++;
            
        }
    }

    
}

void prufer2tree()
{
    for (int i = 1; i <= n + m - 2; i ++ ) d[p[i]] ++;
    p[n + m - 1] = n + m;

    for (int i = 1, j = 1; i < n + m; i ++, j ++ )
    {
        while (d[j]) j ++ ;
        f[j] = p[i];
        while (i < n + m - 1 && -- d[p[i]] == 0 && p[i] < j) f[p[i]] = p[i + 1], i ++ ;
    }

    for (int i = 1; i <= n + m - 1; i ++ ) printf("%d %d\n",i, f[i]);
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &ka, &kb);
    if(ka > m - 1 || kb > n - 1) cout << "No";
    else{
    tree2prufer();
    memset(d, 0, sizeof d);
    for(int i = n + m - 2; i >= 1; i --) p[i] = p[i - 1];
    //for (int i = 1; i <= n + m - 2; i ++ ) printf("%d ", p[i]);
    cout << "Yes\n";
    prufer2tree();
    }

    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 170ms, 内存消耗: 14232K, 提交时间: 2023-08-09 14:54:32

#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int n, m, ka, kb;
    std::cin >> n >> m >> ka >> kb;

    std::vector<int> a(ka), b(kb);
    for (int i = 0; i < ka; ++ i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < kb; ++ i) {
        std::cin >> b[i];
    }

    if (a.size() > m - 1 || b.size() > n - 1) {
        std::cout << "No\n";
        return 0;
    }

    std::cout << "Yes\n";

    while (a.size() < m - 1) {
        a.emplace_back(a.back());
    }
    while (b.size() < n - 1) {
        b.emplace_back(b.back());
    }

    std::multiset<int> prufer;
    std::priority_queue<int, std::vector<int>, std::greater<>> unused;

    for (auto x : a) {
        prufer.emplace(x);
    }
    for (auto x : b) {
        prufer.emplace(x);
    }

    for (int i = 1; i <= n + m; ++ i) {
        if (prufer.find(i) == prufer.end()) {
            unused.emplace(i);
        }
    }

    ka = 0, kb = 0;
    std::vector<std::pair<int, int>> edge;
    for (int i = 0; i < n + m - 2; ++ i) {
        auto x = unused.top();
        int y;
        unused.pop();
        if (x <= n) {
            y = b[kb ++];
        }
        else {
            y = a[ka ++];
        }

        edge.emplace_back(x, y);
        prufer.erase(prufer.find(y));
        if (prufer.find(y) == prufer.end()) {
            unused.emplace(y);
        }
    }

    auto x = unused.top();
    unused.pop();
    auto y = unused.top();

    edge.emplace_back(x, y);

    for (auto [x, y] : edge) {
        std::cout << x << " " << y << "\n";
    }

    
    return 0;
}