题目大意

定义 $k$ 阶刺猬树：

• 对于 $1$ 阶刺猬树，其中一个点的度 $\ge3$，其它点的度均为 $1$。
• 对于 $k$ 阶刺猬树，是在 $k−1$ 阶刺猬树的基础上，把所有度为 $1$ 的点替换成 $1$ 阶刺猬树，并与原图相连。

给定 $n$ 个点的树，判断是否是 $k$ 阶刺猬树。

思路

对于任意 $k$ 阶刺猬树，有性质：

• 假定 $a$ 为原始 $1$ 阶刺猬树的度 $\ge 3$ 的节点，则 $a$ 到所有叶子节点的距离均为 $k$。

而且只要满足此性质及为 $k$ 阶刺猬树。

证明：

假设 $a$ 为 $1$ 阶刺猬树的度 $\ge 3$ 的节点，那么所有的节点到 $a$ 的距离均为 $1$。

$2$ 阶刺猬树则将所有度为 $1$ 的节点增加一层，及将 $a$ 到叶子节点的距离增加 $1$。

对于 $k$ 阶刺猬树，$a$ 到叶子的节点均为 $k-1$ 阶刺猬树到叶子的节点的距离加 $1$，所以 $k$ 阶刺猬树中 $a$ 到叶子节点的距离为 $k$。

相对的，将所有的叶子节点都向父节点移动，那么如果所有的移动经过 $k$ 次移动，到最后在一个节点汇合那么这棵树就是 $k$ 阶刺猬树。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+6;
int n,k,du[N];
bool vis[N];
vector<int> v[N];
queue<int> q[2];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>k;
	if(k>n){
		cout<<"No\n";
		exit(0);
	}
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
		du[x]++,du[y]++;
	}
	for(int i=1;i<=n;i++){
		if(du[i]==1){
			q[1].push(i);
			vis[i]=1;
			// cout<<i<<' ';
		}
	}
	// cout<<'\n';
	// exit(0);
	for(int i=1;i<k;i++){
		while(!q[i%2].empty()){
			int x=q[i%2].front();
			q[i%2].pop();
			for(int j:v[x]){
				if(vis[j]){
					continue;
				}
				if(du[j]<=3){
					cout<<"No\n";
					exit(0);
				}
				// cout<<j<<' ';
				vis[j]=1;
				q[(i+1)%2].push(j);
			}
		}
		// cout<<'\n';
	}
	int cnt=0,p;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cnt++;
			p=i;
			if(du[i]<3){
				cout<<"No\n";
				exit(0);
			}
		}
	}
	if(cnt==1&&q[k%2].size()==v[p].size()){
		cout<<"Yes\n";
	}
	else{
		cout<<"No\n";
	}

	return 0;
}