2020牛客暑期多校训练营(第二场)Cover the Tree 题解(dfs序)
程序员文章站
2022-04-09 10:53:45
题目链接题目大意给一棵树,要求选择最少的点对,所有点对连成的链要覆盖所有的边。边可以重复覆盖,求最少的点对,以及写出点对题目思路首先你从以一个度不为1的点作为根节点。然后你每次都连接一个叶子节点,这样显然是所有的边都可以被覆盖。即答案为度为1的点的个数,但是这样显然很大,可以优化,可以相当于把根节点当作中间节点,让叶子节点两两相连,显然答案已经出来了,就是叶子+12\frac{叶子+1}{2}2叶子+1但是怎么两两配对是一个问题,我比赛的时候差不多已经想到了dfs序,但是还是没写出来,下面就直接...
题目链接
题目大意
给一棵树,要求选择最少的点对,所有点对连成的链要覆盖所有的边。边可以重复覆盖,求最少的点对,以及写出点对
题目思路
首先你从以一个度不为1的点作为根节点。然后你每次都连接一个叶子节点,这样显然是所有的边都可以被覆盖。即答案为度为1的点的个数,但是这样显然很大,可以优化,可以相当于把根节点当作中间节点,让叶子节点两两相连,显然答案已经出来了,就是但是怎么两两配对是一个问题,我比赛的时候差不多已经想到了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
推荐阅读
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第二场)C Cover the Tree
-
2020牛客暑期多校训练营(第二场)Cover the Tree 题解(dfs序)
-
2020牛客暑期多校第二场题解
-
2020牛客暑期多校第二场 C - Cover the Tree(思维/贪心)
-
2020牛客暑期多校训练营(第二场)Cover the Tree 题解(dfs序)
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第二场)A、B、C、D、F、G、J题解及补题
-
2020牛客暑期多校第二场题解