2020牛客暑期多校训练营（第二场）Cover the Tree 题解（dfs序）

题目链接

题目大意

给一棵树，要求选择最少的点对，所有点对连成的链要覆盖所有的边。边可以重复覆盖，求最少的点对，以及写出点对

题目思路

首先你从以一个度不为1的点作为根节点。然后你每次都连接一个叶子节点，这样显然是所有的边都可以被覆盖。即答案为度为1的点的个数，但是这样显然很大，可以优化，可以相当于把根节点当作中间节点，让叶子节点两两相连，显然答案已经出来了，就是$\frac{叶子+1}{2}$但是怎么两两配对是一个问题，我比赛的时候差不多已经想到了dfs序，但是还是没写出来，下面就直接看标程吧。

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define debug printf("I am here\n");
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int n,deg[maxn],head[maxn],ans[maxn],root,tot,cnt;
struct node{
    int to,next;
}e[maxn<<1];
vector<int > vec;
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    deg[u]++;
}
void dfs(int son,int fa){
    if(deg[son]==1){
        ans[++tot]=son;
    }
    for(int i=head[son];i;i=e[i].next){
        if(e[i].to==fa) continue;
        dfs(e[i].to,son);
    }
}
signed main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<=n-1;i++){
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(deg[i]!=1){
            root=i;
            break;
        }
    }
    dfs(root,root);
    int half=(tot+1)/2;
    printf("%d\n",half);
    if(tot%2==1){
        ans[++tot]=root;
    }
    for(int i=1;i<=half;i++){
        printf("%d %d\n",ans[i],ans[i+half]);
    }
    return 0;
}

本文地址：https://blog.csdn.net/m0_46209312/article/details/107325599