欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

2020牛客暑期多校训练营(第二场)C Cover the Tree

程序员文章站 2022-07-03 18:26:34
这题比赛的时候想了半天,码了出来后发现是错的,当场无语,后来hl学长告诉先跑一遍dfs序然后记录一下度为1的点出现的顺序,再输出。具体代码讲#include#include#include#include#include#include#include#include

这题比赛的时候想了半天,码了出来后发现是错的,当场无语,
后来hl学长告诉先跑一遍dfs序然后记录一下度为1的点出现的顺序,再输出。具体代码讲

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<deque>
#include<map>
#include<stdlib.h>
#include<set>
#include<iomanip>
#include<stack>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x & -x
#define fi first
#define se second
#define lson num<<1
#define rson num<<1|1
#define bug cout<<"----acac----"<<endl
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 2e5+ 50;
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
const ll  lnf  = 0x3f3f3f3f3f3f3f3f;
const ll mod = 23333;
const  double pi=3.141592653589;
vector<int>ve[maxn];
int vis[maxn],pa[maxn],cnt;
void dfs(int u,int fa)
{
    if(ve[u].size()==1)//记录度为一的点,也就是叶子节点
    {
        vis[++cnt]=u;
    }
    for(int i=0;i<ve[u].size();i++)
    {
        int v=ve[u][i];
        if(fa==v)continue;
        dfs(v,u);
    }
}
int main()
{
    ms(pa,-1);
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        ve[u].push_back(v);
        ve[v].push_back(u);
        pa[v]=u;
    }
    int root=1;
    cnt=0;
    while(pa[root]!=-1)root++;
    dfs(root,-1);
    printf("%d\n",(cnt+1)/2);//(叶子节点数+1)/2至于为什么自己画一下图就知道了
    for(int i=1;i<=cnt/2;i++)
    {
        printf("%d %d\n",vis[i],vis[i+(cnt+1)/2]);//我一开始写成了printf("%d %d\n",vis[i],vis[n-i+1]);这是错了,当n为偶数的时候可能就匹配到了同一颗子树上的两个叶子节点,那么他们父亲上面的那一条边就覆盖不了了所以是错的
    }
    if(cnt&1)
    {
        printf("%d %d\n",root,vis[(cnt+1)/2]);
    }
    return 0;
}

本文地址:https://blog.csdn.net/qcccc_/article/details/107355260