CF1067B Multihedgehog 题解

发布于 2020-09-13  490 次阅读


题意

题目链接

定义一棵树 k-multihedgehog:

对于 1-multihedgehog,其中一个点度数 $\ge3$ ,其它点度数均为 $1$.

k-multihedgehog 是在 k-1-multihedgehog 的基础上,把所有度为 $1$ 的点替换成一个 1-multihedgehog 并与原图相连。

解析

我们可以用模拟的做法来解决这个问题。我们先假设给出的树是 k-multihedgehog 然后由外自内一层一层删除并记录删了几层,最后再将我们得到的层数与 $k$ 进行比较,判断是否相同即可。当然,如果在模拟过程中发现了不合题意的情况,就直接输出 No 并退出。

那模拟具体怎么实现呢?

我们可以先把最外层的点抽出来,然后找到他们的父亲节点,再将这个父亲节点处理了,处理完这个父亲节点的同时把这个父亲节点推进队列里去,成为下一轮的“最外层的点”,如此往复。同时,由于相邻两层要分开处理,我们需要两个队列滚一下。

这么讲可能不是很清楚,代码会注释的比较详细。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,K;
struct edge{
    int to,next;
}e[N<<1];
int head[N],cnt,num;
int vis[N];
int in[N];
inline void add(int x,int y){
    e[++cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
inline void solve(){
    queue<int> q[2];
    for(int i=1;i<=n;i++)
        if(in[i]==1) q[0].push(i),vis[i]=0;//推进最外层的点 
    for(int t=0;;t^=1){//相邻两层不能混淆,因此需要用 t 标记一下 
        while(!q[t].empty()){
            int x=q[t].front();q[t].pop();
            if(in[x]==0) continue;//如果这个点已经被处理过了,即度数减为 0 了,直接 continue 即可 
            int u;
            for(int i=head[x];i;i=e[i].next){//寻找父亲节点 
                if(in[e[i].to]==0) continue;
                u=e[i].to;break;
            }
            if(in[u]<3){printf("No\n");exit(0);}//如果父亲节点度数 <3,显然是不合题意的 
            int tot=0;//tot 记录儿子个数 
            for(int i=head[u];i;i=e[i].next){
                int v=e[i].to;
                if(in[v]==1&&vis[v]==t) in[v]--,in[u]--,tot++;//对于找到的儿子,父亲和儿子都处理一下 
            }
            if(tot<3){printf("No\n");exit(0);}//如果非最外层节点的儿子数 <3,显然是不合题意的 
            q[t^1].push(u);vis[u]=t^1;
//            printf("out%d %d %d %d\n",x,u,t,num);
        }
        if(q[t^1].empty()) break;//如果下一轮是 empty ,那么说明我们已经找到最终的初始父亲了,可以退出 
        num++;
    }
}
int main(){
    scanf("%d%d",&n,&K);
    memset(vis,-1,sizeof(vis));
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
        in[x]++;in[y]++;//初始记录度数 
    }
    if(K>=n){printf("No\n");return 0;}//显然,层数大于点数直接输出 No (题面 k的范围特别大) 
    solve();
    if(num==K) printf("Yes\n");//若模拟得到的层数和给出的相同,输出 Yes 
    else printf("No\n");
    return 0;
}

如果对代码理解仍然有困难,可以注意代码里有一行被注释掉的 printf ,对于样例 $1$ ,输出结果是这样的:

out1 4 0 0
out7 6 0 0
out10 5 0 0
out4 13 1 1

我们可以看到,该程序先找到了最外层的 $1$ 号点,然后处理了父亲 $4$ 号点,这样三次处理了第一层,然后找到了第二轮成为最外层的 $4$ 号点,处理了他的父亲 $13$ 号点,最后 $13$ 号点处理之后得到的下一层是 empty 的,循环就结束了,除初始根以外找到了 $2$ 层,与 $k$ 相同,故结果为 Yes

琐记

拿到这题的时候,我真的觉得……挺简单,结果一直 WA ,发现这道题坑点很多,处理也算是比较麻烦。此外,不直接从外向内处理,而是每次找父亲节点处理最外层的思路也算是比较有趣的了。


月流华 岁遗沙 万古吴钩出玉匣