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

本文主要是介绍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;
}