Cover the Tree

文章目录

题意：

一个无向树，选择最少数量的链子，能将树上所有边覆盖，答案不唯一
(1≤n≤2×105）
链子就是两点之间的边
看看样例
输入

5
1 2
1 3
2 4
2 5

输出

2
2 3
4 5

一种情况如图所示：
所有边被覆盖的链子有：
链子2->3:覆盖了边1-2,1-3
链子4->5:覆盖了边4-2,2-5

题解：


上述文字看不懂也没关系，我也不大懂，我结合题解谈谈我的认识
所用知识：
dfs序讲解
题目要求我们找链，链有两个端点，其实说白了就是在树上两两找点，让他们匹配，要覆盖所有边
如果有x个叶子节点，那我们最少的子链也要是（x/2）向上取整（不然不能覆盖所有与叶子节点相连的边）
我们让根左子树的叶节点和根右子树的叶节点一一配对，如果叶节点是奇数个的话，再任意找一个节点与之配对即可。

如果任意叶子节点匹配
如图
很容易造成遗漏，比如1——3这条边就没有，

所以我们要按照每种特定的顺序来实现不遗漏，而且所用链不多

我们用dfs序对每个点进行编号，让x与x+（n/2）交叉匹配，这样就不重复了，
最后跑一遍dfs序，记录一下叶子节点出现的位置进行输出

代码

#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int maxn=2e5+7;
vector<int> vec[maxn];
vector<int>sum; 
void dfs(int x,int pre)
{
     
	if(vec[x].size()==1)sum.push_back(x);//将每个叶子节点存放入 
	for(auto i:vec[x])
	{
   
		if(i==pre)continue;
		dfs(i,x);
	}
}
int main()
{
   
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
   
		int u,v;
		cin>>u>>v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int root=1;
	while(vec[root].size()==1)root++;//我们要选的根节点不能只连接一个边
	dfs(root,-1);//dfs序 
	int size=sum.size();
	int ant=(size+1)/2;//另一个点的编号 
	cout<<ant<<endl;
	if(size&1)sum.push_back(root);//如果奇数个点，则将根和多的叶子节点匹配 
	for(int i=0;i<ant;i++)
	{
   
		cout<<sum[i]<<" "<<sum[i+ant]<<endl;
	}
	return 0; 
 }