题目概述

有一棵树，切掉一条树边后会得到两棵树，求出两棵树中的最大编号，记为 $(x,y)$ 。现在给出 $(\{x_{n-1}\},\{y_{n-1}\})$ 。求出一棵满足的树。

解题报告

我连1000+人做的题都不会做，我要菜死了。首先如果 $y<n$ 那么肯定无解，接下来以 $n$ 为根，对于一个 $x$ ，如果出现了 $sum_x$ 次那么说明 $x$ 的深度为 $sum_x$ ，$x$ 到 $n$ 路径上的点不超过 $x$ ，并且 $x$ 不能和其他出现过的 $x'$ 在同一棵子树中（否则就算深度为 $sum_x$ 也不一定出现 $sum_x$ 次）。

所以就可以这么贪心：先把 $sum_x>0$ 中大的 $x$ 用大的 $sum_{y}=0,y<x$ 安排一下，再安排小的。

示例程序

#include<cstdio>
using namespace std;
const int maxn=1000;

int n,sum[maxn+5],dep[maxn+5],top[maxn+5];bool us[maxn+5],vis[maxn+5][maxn+5];

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(scanf("%d",&n),1);i<n;i++)
        {int x,y;scanf("%d%d",&x,&y);if (y<n) return puts("NO"),0;sum[x]++;}
    for (int i=1;i<=n;i++) if (sum[i]) top[i]=n;
    for (int i=n;i;i--)
        if (sum[i]){
            while (sum[i]>1){
                int j;for (j=i;j;j--) if (!sum[j]&&!us[j]) break;if (!j) return puts("NO"),0;
                vis[top[i]][j]=true;top[i]=j;sum[i]--;us[j]=true;
            }vis[top[i]][i]=true;
        }
    puts("YES");for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (vis[i][j]) printf("%d %d\n",i,j);return 0;
}