【链接】

【题意】

【题解】

找到度数为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 
    
     #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
     
       g[N+10];bool flag[N+10];vector
      
        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;}