题意

题目链接

定义一棵树 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 ，发现这道题坑点很多，处理也算是比较麻烦。此外，不直接从外向内处理，而是每次找父亲节点处理最外层的思路也算是比较有趣的了。