1500*C. Kefa and Park（dfs&tree）

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
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;isize();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
		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;
}