Cover the Tree
@[toc]

题意：

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

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; 
 }