Cover the Tree

链接：https://ac.nowcoder.com/acm/contest/5667/C
来源：牛客网

题目描述:

Given an unrooted tree, you should choose the minimum number of chains that all edges in the tree are covered by at least one chain. Print the minimum number and one solution. If there are multiple solutions, print any of them.

输入描述：

The first line contains one integer n(1<=n<=2e5), denoting the size of the tree.
Following n−1 lines each contains two integers u,v (1≤u<v≤n), denoting an edge in the tree.
It's guaranteed that the given graph forms a tree.

输出描述：

The first line contains one integer k, denoting the minimum number of chains to cover all edges.
Following k lines each contains two integers u,v(1≤u,v≤n), denoting a chain you have chosen. Here u=v is permitted, which covers no edge.

solution

将树建成一个无向图，然后对度不为1的某个点进行深搜遍历，记录度为1的叶子节点的序号，如果叶子节点为奇数，那么在数组最后加上一个根节点的序号。然后将数组第一个点与后半部分的第一个节点配对，依次下去

#include<bits/stdc++.h>
using namespace std;
vector<int> e[200005];
int n,u,v;
int vis[200005];
int cnt[200005],t=0;
void dfs(int now)
{
    //cout<<now<<endl;
    vis[now]=1;
    if(e[now].size()==1)
    {
        cnt[t++]=now;
        //cout<<now<<endl;
        return ;
    }
    for(int i=0;i<e[now].size();i++)
    {
        if(vis[e[now][i]])continue;
        dfs(e[now][i]);
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if(e[i].size()>1)
        {
            //cout<<1;
            dfs(i);
            if(t%2==1)
                cnt[t++]=i;
            break;
        }
    }
    cout<<(t+1)/2<<endl;
    for(int i=0;i<t/2;i++)
    {
        cout<<cnt[i]<<' '<<cnt[t/2+i]<<endl;
    }
}