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