题目链接
题意
题目的意思挺难懂的，简单的来说，就是判断一个
k
k
k叉树是否由一个
k
−
1
k-1
k−1叉树而来。这里对
k
k
k叉树的定义是:
对于
1
1
1叉树，仅有一个点度数为
3
3
3且度数为
1
1
1的点个数大于等于3。对于
k
(
k
≥
2
)
k(k\geq2)
k(k≥2)叉树，是一个点连接
3
3
3个或
3
3
3个以上的
(
k
−
1
)
(k-1)
(k−1)叉树所构成。
题解
这题主要就是需要找到树根，如果找到了树根那么就可以进行dfs判断是否为合格的k叉树，但如果找树根呢？一种办法是求出树的直径，然后根据直径长度的一半找到树根，还有一种方法便是，由于这颗树是一层一层扩展出去的，所以只要一层一层往里走，就可以找到树根，类似圆慢慢缩小。 因为每层都是一样的，所以dfs判断的话就是递归k层判断即可（注意特殊处理一下最后一层）。
代码
#include <bits/stdc++.h>
using namespace std
;
const int maxn
= 1e5+5;
vector
<int> G
[maxn
];
int que
[maxn
], l
,r
, de
[maxn
], pre
[maxn
];
void add(int f
,int t
) {
G
[f
].push_back(t
);
}
int bfs(int o
) {
l
= r
= 0;
que
[r
++] = o
;
memset(de
, -1, sizeof de
);
de
[o
] = 0;
pre
[o
] = -1;
while(l
<= r
) {
int u
= que
[l
++];
for(int i
= 0; i
< G
[u
].size(); ++i
) {
int to
= G
[u
][i
];
if(de
[to
] != -1) continue;
pre
[to
] = u
;
de
[to
] = de
[u
]+1;
que
[r
++] = to
;
}
}
return que
[r
-1];
}
bool check(int o
, int fa
, int k
) {
if(k
== 0) {
int son
= 0;
for(int i
= 0; i
< G
[o
].size(); ++i
) {
int to
= G
[o
][i
];
if(to
== fa
) continue;
son
++;
}
if(son
> 0) return false;
return true;
}
int cnt
= 0;
for(int i
= 0; i
< G
[o
].size(); ++i
) {
int to
= G
[o
][i
];
if(to
== fa
) continue;
if(!check(to
, o
, k
-1)) return false;
cnt
++;
}
if(cnt
< 3)
return false;
return true;
}
int main() {
int n
,k
,u
,v
;
scanf("%d%d", &n
, &k
);
for(int i
= 0; i
< n
-1; ++i
) {
scanf("%d%d", &u
, &v
);
add(u
,v
); add(v
,u
);
}
u
= bfs(1);
v
= bfs(u
);
if(de
[v
]%2 != 0)
puts("No");
else {
int center
= v
;
for(int i
= 0; i
< de
[v
]/2; ++i
)
center
= pre
[center
];
if(check(center
, -1, k
))
puts("Yes");
else
puts("No");
}
return 0;
}
