题意
定义 \(1\) 阶“刺猬图” 为一个点度数 \(\ge3\)，其他点度数为 \(1\) 的树。
把一个 \(1\) 阶“刺猬图” 中所有度数为 \(1\) 的点替换成以它为根的 \(1\) 阶“刺猬图”，这样的树称作 \(2\) 阶“刺猬图”。
以此类推。
给定一棵 \(n\) 个点的树和整数 \(k\)，如果该树是 \(k\) 阶“刺猬图”，输出 Yes，否则输出 No。
分析
思路挺简单。
首先找到树的中心，就是作为“刺猬图” 时的根节点，然后跑一遍 DFS，求解出每个点的高度和儿子数，判断即可。
但有个问题是怎么求中心。
WA#1
如果 \(k\ge n\)，肯定输出 No。
先求树的直径，因为它是一棵树，所以满足 \(dis_i\) 为直径一半的 \(i\) 肯定是中心。
然后就 WA 了，看样例 1 可以发现，直径是 \(4\)，但跑出来 \(dis\) 是 \(2\) 的不止一个。
WA#2
经过观察可以发现 \(dis\) 为直径一半的可能是叶子节点，所以加入特判，可过样例，但是还是 WA。
再手造一组数据发现这种节点不一定是叶子节点。
WA#3
两次 DFS 求高度和度数，原理和前面类似，所以也 WA。
AC
如果从叶子节点标记高度为 \(1\)，那么根节点肯定是 \(k+1\)，所以可以搜一遍，然后记录 \(dep\)，如果有多个点都是 \(k+1\)，那么就肯定不满足“刺猬图” 的性质。
后面就很好写了，总时间复杂度 \(O(n)\)。
Code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define dbg(x) cout<<#x<<": "<<x<<"\n"
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
const ll mod=1e9+7,maxn=1e5+5,maxt=505;
ll n,k,dis[maxn],rt,dep[maxn];
vector<ll>son[maxn];
inline void dfs1(ll u,ll pre){
ll mx=0;
dep[u]=dep[pre]+1;
for(auto v:son[u]){
if(v==pre)continue;
dfs1(v,u);
mx=max(mx,dis[v]);
}
dis[u]=mx+1;
}
inline bool dfs2(ll u,ll pre){
ll cnt=0;
for(auto v:son[u]){
if(v==pre)continue;
++cnt;
}
if(dep[u]==k+1)return !cnt;
if(cnt<3)return 0;
for(auto v:son[u]){
if(v==pre)continue;
if(!dfs2(v,u))return 0;
}
return 1;
}
signed main(){
n=read(),k=read();
if(k>=n)puts("No"),exit(0);
for(ll i=1;i<n;++i){
ll u=read(),v=read();
son[u].push_back(v);
son[v].push_back(u);
}
dfs1(1,0);
for(ll i=1;i<=n;++i){
if(dis[i]==k+1){
if(rt)puts("No"),exit(0);
else rt=i;
}
}
dfs1(rt,0);
puts(dfs2(rt,0)?"Yes":"No");
return 0;
}