2020牛客暑期多校第二场题解
程序员文章站
2022-06-23 09:41:37
持续填坑中…ABC原题链接题意:给你一个n个节点的无根树,现在要你找到最少的k条链使得这k条链能覆盖整个树边题解:#include 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 &...
持续填坑中…
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
上一篇: 荐 自创的安卓代码生成器-生成Activity类和布局文件
下一篇: Python初学者第三天
推荐阅读
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
2020牛客多校第三场-J Just Shuffle
-
2020牛客多校第3场[Clam and Fish+贪心]
-
2020牛客多校第三场 E Two Matchings
-
2020牛客暑期多校训练营(第二场)Cover the Tree