树与dfs

题目来源：https://ac.nowcoder.com/acm/contest/5667/C

题意：给一棵没有根的树，连接其中两个节点组成一条链，使树中的每一条边至少被一条链覆盖。 输出最少的链数量+其中任一个解决方案。
做题历程：比赛中我看了这道题老半天，没有想到一个好的结构将这样的树储存起来，而且一开始题意不是太明白，后来才发现到底是个什么意思...也没有想到一个好的解决办法将路径输出。
赛后看出题解后反思思路：
如上图所示，这个最少链数量其实和叶子节点的个数有关（如图中所示），分两种情况，当叶子节点数目为偶数，直接除以二，当叶子节点数目为奇数，除以二加一。可以用dfs来遍历，找出叶子节点的数目。但是有一个注意点就是，方案里的路径可能会涉及相邻的叶子节点（如图样例1），所以要想法规避这一点。具体见代码：

#include<bits/stdc++.h>
using namespace std;

int n,flag,t=0; 
int a[200001];
vector<int> v[200001];//用向量的形式存储这个树 

void dfs(int x,int y)//dfs来统计叶子节点数，x为当前节点，y为其x的双亲节点  
{
    for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=y) 
        dfs(v[x][i],x);

    if(v[x].size()==1)   
    {
        t++;              
         a[t]=x;
    }

}
int main()
{
    int i,x,y;
    int t1;
    cin>>n;
    for(i=1;i<n;i++)            //存储这个树 
    {
       cin>>x>>y;
        v[x].push_back(y);      
        v[y].push_back(x);
    }

    if(n==1) 
    cout<<"0"<<endl;
    else if(n==2) 
    cout<<"1"<<endl<<"1 2"<<endl;
    else
    {
        for(i=1;i<=n;i++)         //找到一个非叶子节点 
            if(v[i].size()>1)
            {
                dfs(i,i);
                flag=i;
                break;
            }
        if(t%2==0)               //这个t1来存最后结果 
            t1=t/2;
        else
            t1=t/2+1;
        cout<<t1<<endl;
        for(i=1;i<=t/2;i++)
         cout<<a[i]<<" "<<a[t1+i]<<endl;
        if(t%2==1) 
        cout<<flag<<" "<<a[t1]<<endl;
    }
    return 0;
}