当前位置： 移动技术网 > IT编程>开发语言>Java > 2020牛客暑期多校训练营（第二场）Cover the Tree

2020牛客暑期多校训练营（第二场）Cover the Tree

2020年07月15日  | 移动技术网IT编程  | 我要评论

Cover the Tree

题目大意：
给定一个无根树，你需要选择最少数量的链，使得树上的所有边都被至少一条链覆盖。输出最少数量，和对应的解。如果有多解，输出任意一个即可。**
输入：
第一行：n (1≤n≤2×10^5)
接下来n-1行每行包含两个整数u,v(1 ≤u < v ≤n)表示节点u和v之间有一条双向边
输出：
第一行输出一个整数k，表示覆盖所有边的最少链数
接下来k行输出两个数u，v，表示节点u和v之间有一条链
样例输入：

5
1 2
1 3
2 4
2 5

样例输出：

2
2 3
4 5

用类似于DFS序的方法将每个叶子节点编号，求出叶子结点个数ans，链的条数就是ans/2向上取整，考虑到每一条边都要被链覆盖，所以第i个叶子节点需要和第ans/2+i个叶子节点相匹配
代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+5;
vector<int> vec[MAXN];
int n,u,v,ans,a[MAXN];
void dfs(int x,int fa)
{
	if(vec[x].size()==1) a[++ans]=x;
	for(int i=0;i<vec[x].size();i++)
	{
		int y=vec[x][i];
		if(y==fa) continue;
		dfs(y,x);
	}
}//求叶子节点的数量和顺序
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	if(n==2) printf("1\n%d %d\n",u,v);
	for(int i=1;i<=n;i++)
    	if(vec[i].size()>1){dfs(i,-1);break;}
	printf("%d\n",(ans+1)/2);
	for(int i=1;i<=(ans+1)/2;i++)
		printf("%d %d\n",a[i],a[i+ans/2]);
}

本文地址：https://blog.csdn.net/s260127ljy/article/details/107335823

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网