$1 - multihedgehog$ 满足：
是一棵树存在一个中心节点$u$与其它所有点相连包括中心节点在内，至少$4$个节点
$2 - multihedgehog$ 刺猬图满足：
是一棵树存在一个中心节点$u$与其它所有$1 - multihedgehog$的中心节点相连
这个中心节点至少连接$3$个以上的$1 - multihedgehog$
$k- multihedgehog$依次类推，给你一棵树，问你它是不是$k- multihedgehog$
看见样例图第一感觉合法图直径都是等长并且经过最开始的那个根。。并且是直径的中点(直径奇数长图不合法，也就是树的中心)，所以求一下树的直径然后找到中点即可。从起点搜完直径终点后再从起点搜如果搜到终点则返回真，标记这些点，这些点在直径上，然后再枚举找到距离是直径一般而且在直径上的点，这个点就是树的中心。
注意特判问题
1一个点的图不合法
2直径奇数长不合法
3直径不等于 $ 2k $ 不合法
知识点：
1、思路写稍微详细一点(check:怎么做)，不要忘记一些判断
2、直径的 dfs 想好再写
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
int zjlen, ct, st, ed, n, k, dis[MAXN], vis[MAXN];
vector<int> G[MAXN];
void dfs(int u, int fa) {
dis[u] = dis[fa] + 1;
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa) dfs(v, u);
}
}
int dfs2(int u, int fa) {
if (u == ed) {vis[ed] = 1; return true;}
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa) {
if (dis[v] == dis[u] + 1) {
int gg = dfs2(v, u);
if (gg) {vis[u] = 1; return true;}
}
}
}
return false;
}
int check(int u, int fa, int dep) {
int dg = 0;
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa) ++dg;
}
if (dep == zjlen / 2) {
if (dg != 0) return false;
return true;
}
if (dg < 3) return false;
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa) {
if (!check(v, u, dep + 1)) return false;
}
}
return true;
}
void clean() {
ms(vis, 0), ms(dis, 0);
}
int solve() {
cin >> n >> k;
if (n == 1) return printf("No\n"), 0;
clean();
for (int u, v, i = 1; i < n; ++i) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
dis[0] = 0, dfs(1, 0);
st = 0;
for (int i = 1; i <= n; ++i) if (dis[i] > dis[st]) st = i;
ms(dis, 0), dfs(st, 0);
ed = 0;
for (int i = 1; i <= n; ++i) if (dis[i] > dis[ed]) ed = i;
zjlen = dis[ed] - 1;
if (zjlen % 2 == 1) return printf("No\n"), 0;
if (zjlen / 2 != k) return printf("No\n"), 0;
ct = 0;
dfs2(st, 0);
for (int i = 1; i <= n; ++i) if (dis[i] - 1 == zjlen / 2 && vis[i]) {ct = i; break;}
if (check(ct, 0, 0)) return printf("Yes\n"), 0; else return printf("No\n"), 0;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
7 2
1 2
2 5
2 6
2 7
1 3
1 4
14 3
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6
*/
