【链接】 我是链接,点我呀:)
【题意】
【题解】
找到度数为1的点。
他们显然是叶子节点。
然后每个叶子节点。
往上进行bfs.
累计他们的父亲节点的儿子的个数。
如果都满足要求那么就继续往上走。
直到不能走。或已经走了k步。
且要求走了k步之后。他们都到了同一个节点。(根节点
这道题。
n=1的时候,认为是无解的。
(因为题目中说"some vertices of degree 1",也就是说必须>= 1.......
【代码】
/*
find each vertex i where du[i]==1
bfs(i) one depth and get y,cnt[y]++;
after that
count the number if different cnt[y] ->CNT (only consider cnt[y]>0
if (CNT!=1) return 0;
set the only cnt value as kk
we can now know that the root has kk children
find the root,(du[root]==kk)
(if there are more than one i such that du[i]==kk,no solution
(if there are no such i,such that du[i]==k,no solution
dfs from root.
if (dep!=k && du[x]==1) return 0;//must have k depth
check if every vertex except the bottom vertext all has kk children
*/
#include <bits/stdc++.h>
#define ll long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
using namespace std;
const int N = 1e5;
int n,k;
vector<int> g[N+10];
bool flag[N+10];
vector<int> v,tempv;
int cnt[N+10];
void wujie(){
puts("No");
exit(0);
}
int main(){
#ifdef ccy
freopen("rush.txt","r",stdin);
#endif
scanf("%d%d",&n,&k);
if (n==1){
puts("No");
return 0;
}
rep1(i,1,n-1){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
rep1(i,1,n)
if ((int)g[i].size()==1){
v.push_back(i);
}
rep1(dep,1,k){
/*
for (int x:v){
printf("%d ",x);
}
puts("");*/
rep1(j,0,(int)v.size()-1){
int x = v[j];
int cntup = 0;
rep1(l,0,(int)g[x].size()-1){
int y = g[x][l];
// printf("%d ",y);
if (flag[y]) continue;
cnt[y]++;
cntup++;
}
if (cntup!=1) wujie();
flag[x] = true;
}
// puts("");
v.clear();
rep1(i,1,n){
if (cnt[i]!=0 && cnt[i]<3) wujie();
if (cnt[i]==0) continue;
v.push_back(i);
cnt[i] = 0;
}
}
rep1(i,0,(int)v.size()-1){
if (v[i]!=v[0]) wujie();
}
puts("Yes");
return 0;
}