原题： http://codeforces.com/contest/1068/problem/E
题意：
K层树定义：上面K层节点都有至少三个儿子，第K+1层全是叶子。给出一棵树结构和K，问这棵树是不是K叉（不知道root）
解析：
首先是dfs得出每个节点的度，度为1的是叶子。然后叶子开始一层一层往上剪，直到剩下一个节点便是root
找root的时候可以当成是K叉，因为如果有root，就是跑出来的这个；如果没有，跑出来的是什么都会被check刷掉
然后从root往下dfs，判断所有叶子是不是同一层，每个节点是不是有至少三个儿子
#include<bits/stdc++.h> using namespace std; int head[100009],nex[200009],to[200009];int now; int de[100009]; int n=100000; void add(int a,int b){ nex[++now]=head[a];head[a]=now;to[now]=b; } void getDegree(int p,int fa){ if(fa!=0)de[p]=1; for(int i=head[p];~i;i=nex[i]){ if(to[i]==fa)continue; de[p]++; getDegree(to[i],p); } } int root; bool vis[100009]; void getRoot(){ queue<int>p[2];int f=0; for(int i=1;i<=n;i++){ if(de[i]==1)p[f].push(i),vis[i]=1; } while(1){ while(!p[f].empty()){ int e=p[f].front();p[f].pop(); for(int i=head[e];~i;i=nex[i]){ if(vis[to[i]])continue; vis[to[i]]=1; p[!f].push(to[i]); } } f=!f; if(p[f].size()<=1){ if(p[f].size()==1)root=p[f].front(); else root=-1; break; } } } int yes=1; int deep=-1; void check(int p,int fa,int v){ if(de[p]==1){ if(deep==-1)deep=v; else if(deep!=v)yes=0; return; } int ct=0; for(int i=head[p];~i;i=nex[i]){ if(to[i]==fa)continue; ct++; check(to[i],p,v+1); } if(ct<3)yes=0; } int main() { memset(head,-1,sizeof(head)); int k;scanf("%d%d",&n,&k); for(int i=2;i<=n;i++){ int a,b;scanf("%d%d",&a,&b); add(a,b);add(b,a); } getDegree(1,0); getRoot(); if(root==-1)return 0*printf("No\n"); check(root,0,0); if(yes&&deep==k)printf("Yes\n"); else printf("No\n"); }