CF1041E Tree Reconstruction 构造题

题意翻译

题目大意：

有一棵树，现在给你每条树边被去掉时，形成的两个联通块中点的最大的编号分别是多少，问满足条件的树存不存在

输入格式：

第一行一个整数nnn

往下n−1n-1n−1行，每行两个整数，表示去掉这条边后两个联通块中点的最大的编号是多少

输出格式：

如果不存在满足条件的树，输出"NO"

否则输出"YES"，下面n−1n-1n−1行每行描述一条树边（两端点的编号）

题目描述

Monocarp has drawn a tree (an undirected connected acyclic graph) and then has given each vertex an index. All indices are distinct numbers from 1 1 1 to n n n . For every edge e e e of this tree, Monocarp has written two numbers: the maximum indices of the vertices of the two components formed if the edge e e e (and only this edge) is erased from the tree.

Monocarp has given you a list of n−1 n - 1 n−1 pairs of numbers. He wants you to provide an example of a tree that will produce the said list if this tree exists. If such tree does not exist, say so.

输入输出格式

输入格式：

 

The first line contains one integer n n n ( 2≤n≤1000 2 \le n \le 1\,000 2≤n≤1000 ) — the number of vertices in the tree.

Each of the next n−1 n-1 n−1 lines contains two integers ai a_i ai​ and bi b_i bi​ each ( 1≤ai<bi≤n 1 \le a_i < b_i \le n 1≤ai​<bi​≤n ) — the maximal indices of vertices in the components formed if the i i i -th edge is removed.

 

输出格式：

 

If there is no such tree that can produce the given list of pairs, print "NO" (without quotes).

Otherwise print "YES" (without quotes) in the first line and the edges of the tree in the next n−1 n - 1 n−1 lines. Each of the last n−1 n - 1 n−1 lines should contain two integers xi x_i xi​ and yi y_i yi​ ( 1≤xi,yi≤n 1 \le x_i, y_i \le n 1≤xi​,yi​≤n ) — vertices connected by an edge.

Note: The numeration of edges doesn't matter for this task. Your solution will be considered correct if your tree produces the same pairs as given in the input file (possibly reordered). That means that you can print the edges of the tree you reconstructed in any order.

 

输入输出样例

输入样例#1： 复制

4
3 4
1 4
3 4

输出样例#1： 复制

YES
1 3
3 2
2 4

输入样例#2： 复制

3
1 3
1 3

输出样例#2： 复制

NO

输入样例#3： 复制

3
1 2
2 3

输出样例#3： 复制

NO

说明

Possible tree from the first example. Dotted lines show edges you need to remove to get appropriate pairs.

 

---

有一棵树，每次去掉一条边自然分成两个部分，每个节点都有一个 index，现给出每次去掉边后两边的最大index ，问能否还原出原来的树，如果可以，输出边的两个端点；

---

思路：

① 很明显，不论去掉哪条边，最大的index一定是 n ，所以如果给出的 index pair 中没有 n ，那么一定是 no；

② 如果一个节点为 k ，那么"子树最大节点<=k的子树数量" <=k；

如果上面两个条件一个没有满足，就是 no ；

 

现在考虑如何去构造；

很显然，我们一定可以构造一条链出来，最后的 root index =n ；然后我们将小的index 排序；

如果 index[ x-1 ]== index [ x ]，那么此时我们遍历还未被使用的index,且 index <x，作为上一个节点的父节点；

如果 index[ x-1 ]<index[ x ]，那么直接将该节点作为上一个的父节点即可；

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
//#include<cctype>
//#pragma GCC optimize("O3")
using namespace std;
#define maxn 500005
#define inf 0x3f3f3f3f
#define INF 999999999999999
#define rdint(x) scanf("%d",&x)
#define rdllt(x) scanf("%lld",&x)
#define rdlf(x) scanf("%lf",&x)
#define rdstr(x) scanf("%s",x)
typedef long long  ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset((x),0,sizeof(x))
const int mod = 10000007;
#define Mod 20100403
#define sq(x) (x)*(x)
#define eps 1e-7
typedef pair<int, int> pii;
#define pi acos(-1.0)
const int N = 1005;
#define REP(i,n) for(int i=0;i<(n);i++)
inline int rd() {
    int x = 0;
    char c = getchar();
    bool f = false;
    while (!isdigit(c)) {
        if (c == '-') f = true;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f ? -x : x;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}
ll sqr(ll x) { return x * x; }

int n;
int sum[maxn];
int ans;
int vis[maxn];
int dfs() {
    for (int i = 1; i < n; i++)if (!vis[i])return i;
}

int main()
{
    //ios::sync_with_stdio(false);
    rdint(n);
    for (int i = 1; i < n; i++) {
        int x, y; rdint(x); rdint(y);
        if (x > y)swap(x, y);
        if (y != n) { cout << "NO" << endl; return 0; }
        sum[x]++;
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        tot += sum[i]; if (tot > i) { cout << "NO" << endl; return 0; }
    }
    cout << "YES" << endl;
    int pre = -1;
    for (int i = 1; i <= n; i++) {
        if (sum[i]) {
            vis[i] = 1;
            if (pre != -1)cout << pre << ' ' << i << endl;
            pre = i; sum[i]--;
        }
        while (sum[i]) {
            int DFS = dfs();
            cout << pre << ' ' << DFS << endl; pre = DFS; vis[DFS] = 1; sum[i]--;
        }
    }
    cout << pre << ' ' << n << endl;
    return 0;
}