c/c++语言开发共享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("0n");return 0;     }     if(n == 2){         printf("1n");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("%dn",(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 %dn",a,b);     }     return 0; } 

D

E

F

G

H

c/c++开发分享2020牛客暑期多校第二场题解地址：https://blog.csdn.net/qq_43597227/article/details/107325018