C. Cover the Tree2020 (dfs序构造) 牛客暑期多校训练营（第二场）

本文主要是介绍C. Cover the Tree2020 (dfs序构造) 牛客暑期多校训练营（第二场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

。在这里插入图片描述

题意：
求最少的链覆盖所有边

思路：
可以想到任意链都得叶子开始叶子结尾，那么数目肯定是确定的，为叶子数目加一除以二。

可以想到，为了尽可能的覆盖更多变，我们要选宽度尽可能大的叶子相连。这里的宽度我们可以用dfs序表示，选择非叶子节点作为根然后求dfs序，然后两两配对。

但不能是最右边的叶子匹配最左边的叶子，
比如 1->2，1->3, 1->4 , 4->5, 4->6中，1->4边就可能覆盖不到。
所以要 a[i]匹配a[i+len/2]。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>using namespace std;typedef long long ll;const int maxn = 2e5 + 7;
const int INF = 0x3f3f3f3f;vector<int>G[maxn];
vector<int>Leaf;
int dfn[maxn],cnt;void dfs(int x,int fa) {dfn[x] = ++cnt;for(int i = 0;i < G[x].size();i++) {int v = G[x][i];if(v == fa) continue;dfs(v,x);}
}int cmp(int x,int y) {return dfn[x] < dfn[y];
}int main() {int n;scanf("%d",&n);for(int i = 1;i < n;i++) {int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}if(n == 1) {printf("0\n");return 0;}if(n == 2) {printf("1\n1 2\n");return 0;}for(int i = 1;i <= n;i++) {if(G[i].size() == 1) {Leaf.push_back(i);}}int rt = 1;for(int i = 1;i <= n;i++) {if(G[i].size() != 1) {rt = i;break;}}dfs(rt,-1);sort(Leaf.begin(),Leaf.end(),cmp);int len = Leaf.size();printf("%d\n",(len + 1) / 2);for(int i = 0;i < len / 2;i++) {printf("%d %d\n",Leaf[i],Leaf[i + len / 2]);}if(len % 2 == 1) {printf("%d %d\n",Leaf[0],Leaf[len - 1]);}return 0;
}