codeforces 580 C. Kefa and Park
http://codeforces.com/contest/580/problem/C
题意：给出一棵树。每个叶子节点上有一个饭店。某些节点上有cat.现在问从根节点出发可以到达多少个饭店，保证在到达饭店的路径中补连续遇到m个以上的cat.
思路：建图，然后dfs..判断为叶子节点（饭店）的方法是某个点的叶子节点数为0.
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月05日 星期六 10时17分01秒
4File Name :580C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25
26
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34
35int m,n;
36bool vis[N];
37vector<int>edge[N];
38int hascat[N];
39int ans;
40
41void dfs( int cur,int num)
42{
43 vis[cur] = true;
44 if (hascat[cur])
45 num++;
46 else num = 0 ;
47
48 // cout<<"cur:"<<cur<<" num:"<<num<<endl;
49
50 if (num>m) return;
51
52 int leafnum = 0;
53 for ( int i = 0 ; i <edge[cur].size(); i++ )
54 {
55 int v = edge[cur][i];
56// cout<<"cur:"<<cur<<" v:"<<v<<endl;
57 if (!vis[v])
58 {
59 dfs(v,num);
60 leafnum++;
61 }
62 }
63 if (leafnum==0) ans++;
64
65}
66int main()
67{
68 #ifndef ONLINE_JUDGE
69 freopen("code/in.txt","r",stdin);
70 #endif
71 ms(vis,false);
72 ms(hascat,0);
73 scanf("%d %d",&n,&m);
74 for ( int i = 1 ; i <= n ; i++) scanf("%d",&hascat[i]);
75 for ( int i = 1 ; i <= n-1 ; i++)
76 {
77 int u,v;
78 scanf("%d %d",&u,&v);
79 edge[u].push_back(v);
80 edge[v].push_back(u);
81 }
82
83 ans = 0 ;
84 dfs(1,0);
85 printf("%d\n",ans);
86
87 #ifndef ONLINE_JUDGE
88 fclose(stdin);
89 #endif
90 return 0;
91}