持续填坑中…
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;
}