cf1041E
2024-09-04 21:36:49
题意:要求你构造一棵树,树中每一个节点都有一个编号(互不相同),告诉你删除掉每一条边之后的两个联通分量中节点标号的最大值,要求你输出这颗树,不存在就输出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);
}
最新文章
- 直接操作 SDL_Overlay YUV叠加上的像素
- php构造方法与析构方法
- linux 软件安装
- C++_快速排序(纯C版本)
- 层层递进Struts1(七)详解DispatchAction
- hdoj 4552 怪盗基德的挑战书【求前缀在字符串中出现的次数之和】
- JAVA异常使用_每个人都曾用过、但未必都用得好
- adb server无法启动方法,结束占用端口的进程
- dBm与Vpp相互转换公式
- HashMap原理阅读
- 51nod 1423 最大二“货” 单调栈
- Python全栈day9习题
- 利用反射编写私有 Private 方法的单元测试
- BZOJ.2565.[国家集训队]最长双回文串(Manacher/回文树)
- Android 真机调试
- [Fiddler] The connection to &#39;xxxxx.com&#39; failed. <;br />;System.Security.SecurityException Failed to negotiate HTTPS connection with server.fiddler.network.https&;gt; HTTPS handshake to intelte
- markdown语法---根据使用不断扩充中
- eclipse Java注释修改
- 理解JAVA虚拟机(上)
- js获取今天,明天,本周五,下周五日期的函数