Cover the Tree 2020牛客第二场
文章目录
题意
给你一颗树,要求构造最少的链,这些链覆盖该树的所有边,输出链数和每一条链的两个端点。
思路
我们很容易想到,这些链的两端应该是叶子节点,设叶子节点个个数为s,那么我们可以构造出s/2的链,使所有边被覆盖,那么现在难点就在,如果让构造的两个端点不是兄弟,例如
如果我们选择(4,5),(6,7)那么这两条链覆盖不了1->2和1->3这两条边。
正解应该是(4,6),(5,7),所以我们考虑如下构造方法:设共s个叶子节点,我们给每个叶子节点编号,令xi和xi+s/2配对,这样构造必有解且链数为(k+1)/2。
证明:
AC代码
include<iostream>
using namespace std;
const int maxn=2e5+5;
int du[maxn],num[maxn];
int n,u,v;
int main()
{
cin>>n;
for(int i=1;i<n;i++){
cin>>u>>v;
du\[u\]++;du\[v\]++;
}
int k=0;
for(int i=1;i<=n;i++){
if(du\[i\]==1){
num\[++k\]=i;
}
}
cout<<(k+1)/2<<'\\n';
for(int i=1;i<=(k+1)/2;i++){
cout<<num\[i\]<<" "<<num\[i+k/2\]<<'\\n';
}
return 0;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论