题意:要求你构造一棵树,树中每一个节点都有一个编号(互不相同),告诉你删除掉每一条边之后的两个联通分量中节点标号的最大值,要求你输出这颗树,不存在就输出NO

题解:可以发现这颗树实际上是一个序列,我们构造一个序列就可以了

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int cnt[N];

int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
if(y != n)
{
puts("NO");
return 0;
}
cnt[x]++;
}
int cur = 0;
for(int i = 1; i < n; i++)
{
cur += cnt[i];
if(cur > i)
{
puts("NO");
return 0;
}
}
int last = -1;
puts("YES");
set<int> unused;
for(int i = 1; i < n; i++)
unused.insert(i);
for(int i = 1; i < n; i++)
{
if(cnt[i] > 0)
{
unused.erase(i);
if(last != -1)
printf("%d %d\n", last, i);
last = i;
cnt[i]--;
}
while(cnt[i] > 0)
{
printf("%d %d\n", last, *unused.begin());
last = *unused.begin();
cnt[i]--;
unused.erase(unused.begin());
}
}
printf("%d %d\n", last, n);
}

  

最新文章

  1. 直接操作 SDL_Overlay YUV叠加上的像素
  2. php构造方法与析构方法
  3. linux 软件安装
  4. C++_快速排序(纯C版本)
  5. 层层递进Struts1(七)详解DispatchAction
  6. hdoj 4552 怪盗基德的挑战书【求前缀在字符串中出现的次数之和】
  7. JAVA异常使用_每个人都曾用过、但未必都用得好
  8. adb server无法启动方法,结束占用端口的进程
  9. dBm与Vpp相互转换公式
  10. HashMap原理阅读
  11. 51nod 1423 最大二“货” 单调栈
  12. Python全栈day9习题
  13. 利用反射编写私有 Private 方法的单元测试
  14. BZOJ.2565.[国家集训队]最长双回文串(Manacher/回文树)
  15. Android 真机调试
  16. [Fiddler] The connection to &#39;xxxxx.com&#39; failed. &lt;br /&gt;System.Security.SecurityException Failed to negotiate HTTPS connection with server.fiddler.network.https&amp;gt; HTTPS handshake to intelte
  17. markdown语法---根据使用不断扩充中
  18. eclipse Java注释修改
  19. 理解JAVA虚拟机(上)
  20. js获取今天,明天,本周五,下周五日期的函数

热门文章

  1. RPC简单设计方案
  2. sizeof(&#39;a&#39;)
  3. hdu 1159求最长公共子序列
  4. LaTeX技巧472:定义一个LaTeX参考文献不带编号且有缩进的方法
  5. java Map排序问题
  6. 技术|Android安装包优化
  7. Go语言实现:【剑指offer】把字符串转换成整数
  8. 《C# 爬虫 破境之道》:第二境 爬虫应用 — 第六节:反爬策略研究
  9. 对MYSQL注入相关内容及部分Trick的归类小结
  10. Html / XHtml 解析 - Parsing Html and XHtml