2020牛客暑期多校训练营（第二场）

C.Cover the Tree

首先你从以一个度不为1的点作为根节点。然后你每次都连接一个叶子节点，这样显然是所有的边都可以被覆盖。即答案为度为1的点的个数，但是这样显然很大，可以优化，可以相当于把根节点当作中间节点，让叶子节点两两相连，显然答案已经出来了，就是(叶子+1)/2

但是怎么两两配对是一个问题，下图提供了证明：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=2e5+7;
int n, m, t, ans[maxn];
int cnt, head[maxn];
int deg[maxn], root;
struct node{
    int nxt,to;
}e[maxn<<1];
void add(int u,int v){
     e[cnt].nxt=head[u];
     e[cnt].to=v;
     head[u]=cnt++;
}
void dfs(int u, int pre){
    if(deg[u]==1) ans[++t] = u;
    for(int i = head[u]; i != -1; i = e[i].nxt){
        int to = e[i].to;
        if(to != pre) dfs(to, u);
    }
}

int main (){
    scanf("%d", &n);
    memset(head,-1,sizeof(head));
    for(int i = 1; i <= n-1; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        add(u,v), add(v,u);
        deg[u]++, deg[v]++;
    }
    for(int i = 1; i <= n; i++){
        if(deg[i]>1){
          root = i;
          break;
        }
    }
    dfs(root, -1);
    if(t%2==1) ans[++t] = root;
    printf ("%d
", t/2);
    for(int i = 1; i <= t/2; i++){
        printf ("%d %d
", ans[i], ans[t/2+i]);
    }
}