2020牛客多校第二场C Cover the Tree （dfs序）

Cover the Tree （dfs序）
链接：https://ac.nowcoder.com/acm/contest/5667/C

题目大意：

给定一颗n个节点的无根树，任意两个结点(可叶子也可根节点)可形成一条链，让你用最少的链经过树上所有的边，然后输出这几条链的两边端点。

*一开始看完这道题想的是要求树的直径，然后把未在直径的叶子节点两两配对，后来一想是错的，因为是要遍历所有的边而不是点，这样有大概率有遗漏。*

回到该题上来，思索一下不难发现，如果有x叶子节点的话，那么**最少子链就是（x/2）向上取整个.

就是要求dfs序，然后根左子树的叶节点和根右子树的叶节点一一配对，如果叶节点是奇数个的话，再任意找一个节点与之配对即可。

下面上图

如若按红线匹配的话（任意叶节点匹配），则出现了1-3遗漏

正解：x于x+(n/2)交叉匹配，则不会出现遗漏。然后跑一下dfs序，记录一下叶子节点的出现位置输出即可。

#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define inf 9654234
#define ll long long
using namespace std;
const int maxn=2e5+7;
int n;
vector ve[maxn],ans;
void dfs(int x,int pre){
    if(ve[x].size()==1) ans.push_back(x);
    for(auto it:ve[x]){
        if(it==pre) continue;
        dfs(it,x);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    int root=1;
    while(ve[root].size()==1) root++;
    dfs(root,-1);
    int sz=ans.size();
    int cnt=(sz+1)/2;
    cout<<cnt<<endl;
    if(sz&1) ans.push_back(root);
    for(int i=0;i<cnt;i++){
        cout<<ans[i]<<" "<<ans[i+cnt]<<endl;
    }
    return 0;
}