CodeForce - 1014E - Tree Reconstruction 贪心

题目链接

题意：一颗树，有n个节点，现在有n-1个状态，第i个状态表示删除第i条边，每个状态有两个数a，b。表示删除第i条边后形成的两棵树分别的最大的节点。求已知n-1个状态，是否存在这样的树，存在则同时把边输出。

思路：因为每个状态肯定存在n，所以只要看另外一个节点。统计一下每个节点出现的次数num。可以发现若num[3]=3，则该树可以为n-1-2-3，若num[3]=2，则可以是2-n-1-3，以此类推，那我们可以把n看作树根，每个节点到树根n都是以链的形式存在，不存在分支，这样可以得出，若num[i]!=0，则i到树根n的距离为num[i]，且路径上的点均小于i且num均为0，所以可以从贪心的角度，从小到大遍历num=0，同时从小到大遍历num!=0，把前一个遍历的节点插入到n和后一个遍历的节点之间即可。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define PI acos(-1)
#define INF 0x3f3f3f3f
#define NUM 50010
#define debug true
#define lowbit(x) ((-x)&x)
#define ffor(i,d,u) for(int i=d;i<=u;++i)
#define _ffor(i,u,d) for(int i=u;i>=d;--i)
#define mst(array,Num) memset(array,Num,sizeof(array))
const int p = 1e9+7;
int n;
int a[1100];
struct ANS
{
    int from,to;
}ans[1100];
int que[1100],head,tail;
int tot=0;
template <typename T>
void read(T &x){
    char ch = getchar();x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
template <typename T>
void write(T x)
{
    int len=0;char c[21];
    if(x<0)putchar('-'),x*=(-1);
    do{++len;c[len]=(x%10)+'0';}while(x/=10);
    _ffor(i,len,1)putchar(c[i]);
}
inline void AC()
{
    int x,y;
    mst(a,0);
    read(n);
    ffor(i,1,n-1)
    {
        read(x),read(y);
        ++a[x],++a[y];
    }
    if(a[n]!=n-1)
    {
        puts("NO");
        return ;
    }
    int j;
    head=1,tail=0;
    ffor(i,1,n-1)
        if(a[i]==0)
            que[++tail]=i;
        else
        {
            j=n,--a[i];
            while(head<=tail&&a[i]!=0)
            {
                x=que[head++];
                if(x>i)break;
                ans[++tot].from=j,ans[tot].to=x,--a[i];
                j=x;
            }
            if(a[i]!=0)
            {
                puts("NO");
                return ;
            }
            ans[++tot].from=j,ans[tot].to=i;
        }
    puts("YES");
    ffor(i,1,n-1)write(ans[i].from),putchar(' '),write(ans[i].to),putchar('\n');
}
int main()
{
    AC();
    return 0;
}