2020牛客暑期多校训练营（第二场）C-Cover the Tree

题目大意

给定一棵无根树，连接其中两个节点组成一条链，使树中的每一条边至少被一条链覆盖。 输出最少的链数量+其中任何一个解决方案。

解题思路

先引用原题的一个（水）测试样例：

5 <--节点数量

1 2 <--节点中连的边（节点数量-1条）

1 3

2 4

2 5

可以得到这样一颗树，我们可以用这样两条链覆盖它的所有边（解决方案不唯一）。

))

面对这种情况，应该怎么遍历呢？

部分代码+注解

先放部分代码，可能更方便理解思路。

先定义一个向量，记录与每个点有连边的节点，构造一棵简单的树。

for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
    v[x].push_back(y);
    v[y].push_back(x);
    }

接下来是开始dfs。先找到一个非叶节点，将其存储。

for(i=1;i<=n;i++)
    if(v[i].size()>1)
    {
        dfs(i,i);
        z=i;
    break;
    } 

存储dfs到的每个叶节点，总数记录为t。

void dfs(int x,int y) //当前节点+父亲节点
{
    for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=y) dfs(v[x][i],x);
    if(v[x].size()==1) t++,a[t]=x;
}

通过 理 智 分 析，可以得出链的最多条数（tt）=叶节点个数/2（向上取整）
输出第L(i)和第L(t/2+i)两个叶节点连成一条链
（本来是想L(1)L(t),L(2)L(t-1)这样分组，但是会有例外）

这样1--3这条边就落单了

if(t%2==0) tt=t/2;
else tt=t/2+1;
printf("%d\n",tt);
for(i=1;i<=t/2;i++)
    printf("%d %d\n",a[i],a[tt+i]);
if(t%2==1) printf("%d %d",z,a[tt]);

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,t,a[200010];
vector v[200010];
void dfs(int x,int y)
{
    for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=y) dfs(v[x][i],x);
    if(v[x].size()==1) t++,a[t]=x;
}
int main()
{
    int i,x,y,z,tt;
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    if(n==1) printf("0\n");
    else if(n==2) printf("1\n1 2");
    else
    {
        for(i=1;i<=n;i++)
            if(v[i].size()>1)
            {
                dfs(i,i);z=i;
                break;
            }
        if(t%2==0) tt=t/2;
        else tt=t/2+1;
        printf("%d\n",tt);
        for(i=1;i<=t/2;i++) printf("%d %d\n",a[i],a[tt+i]);
        if(t%2==1) printf("%d %d",z,a[tt]);
    }
    return 0;
}