1500*C. Kefa and Park（dfstree）

Kefa and Park - 洛谷 

Problem - 580C - Codeforces

Examples

input

4 1
1 1 0 0
1 2
1 3
1 4

output

2

input

7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

output

2

 解析：

        dfs遍历，记录前一个结点权值是否为1，并且累计路径1的个数。        

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,a[N],res;
vector<int>e[N];
void dfs(int u,int cnt,int f,int fa){if(f) cnt+=a[u];else cnt=a[u];if(cnt>m) return;if(e[u].size()==1&&e[u][0]==fa) res++;for(int i=0;i<e[u].size();i++){if(e[u][i]!=fa) dfs(e[u][i],cnt,a[u],u);}
}
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}for(int i=1;i<n;i++){int x,y;scanf("%lld%lld",&x,&y);e[x].push_back(y);e[y].push_back(x);}dfs(1,0,0,-1);printf("%lld",res);return 0;
}