Codeforces Round #509 (Div. 2) E. Tree Reconstruction（构造）

题目链接：http://codeforces.com/contest/1041/problem/E

题意：给出n - 1对pair，构造一颗树，使得断开其中一条边，树两边的最大值为 a 和 b 。

题解：显示最大值出现的次数为n - 1，且i点出现的次数小于等于i。一个数字 i（< n）出现的次数为 i 到 n 的距离，可构造出一条链使得满足条件。

 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define ull unsigned long long
#define mst(a,b) memset((a),(b),sizeof(a))
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pi acos(-1)
#define pii pair<int,int>
#define pb push_back
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int MAXN = 1e3 + 10;
const int MAXM = 2e6 + 10;
const ll mod = 1e9 + 7;

int du[MAXN];

int main()
{
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    int n;
    scanf("%d",&n);
    bool flag = true;
    for(int i = 1; i < n; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        du[a]++;
        if(b != n) flag = false;
    }
    int now = 0;
    for(int i = 1; i < n; i++) {
        now += du[i];
        if(now > i) flag = false;
    }
    if(!flag) {
        puts("NO");
        return 0;
    }
    puts("YES");
    set<int>se;
    for(int i = 1; i <= n; i++) se.insert(i);
    int pre = -1;
    for(int i = 1; i < n; i++) {
        if(du[i]) {
            if(pre != -1) printf("%d %d\n",pre,i);
            pre = i;
            du[i]--, se.erase(i);
        }
        while(du[i]) {
            printf("%d %d\n",pre,*se.begin());
            pre = *se.begin();
            du[i]--, se.erase(se.begin());
        }
    }
    printf("%d %d\n",pre,n);
    return 0;
}