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;
}