2020牛客暑期多校第二场题解

持续填坑中…

A

B

C

原题链接
题意：给你一个n个节点的无根树，现在要你找到最少的k条链使得这k条链能覆盖整个树边

题解：

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
struct edge{
    int v,next;
}e[maxn];

struct node{
    int id;
    int dfn;
    bool operator <(const node &rhs) const{
        return dfn<rhs.dfn;
    }
}p[maxn];

int n;
int dfn[maxn];
int head[maxn],cnt=0;
int deg[maxn];
bool vis[maxn];

void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int ct=0;
void dfs(int x){
    dfn[x]=++ct;
    for (int i=head[x];i;i=e[i].next){
        int v=e[i].v;
        if(!vis[v]){
            vis[v]=1;
            dfs(v);
        }
    }
}

int main(){
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
        deg[u]++;
        deg[v]++;
    }
    if(n == 1){
        printf("0\n");return 0;
    }
    if(n == 2){
        printf("1\n");return 0;
    }
    for (int i=1;i<=n;i++){
        if(deg[i] != 1){//找到第一个非叶节点，把其作为树根，求一个dfs序
            vis[i] = 1;
            dfs(i);
            break;
        }
    }

    int tot = 0;
    for (int i=1;i<=n;i++){
        if(deg[i] == 1){//选出叶子结点
            p[++tot].id = i;
            p[tot].dfn = dfn[i];
        }
    }
    sort(p+1,p+1+tot);

    printf("%d\n",(tot+1)/2);
    for (int i=1;i<=(tot+1)/2;i++){
        int a=p[i].id,b=p[tot/2+i].id;
        printf("%d %d\n",a,b);
    }
    return 0;
}

D

E

F

G

H

本文地址：https://blog.csdn.net/qq_43597227/article/details/107325018