题目描述

在这个问题中，给定一个值 $s$ 和一棵树。

在树的每个节点 $i$ 有一个权值 $a_i$，问有多少条路径的节点权值总和为 $s$。

路径中节点的深度必须是升序的。

假设节点 $1$ 是根节点，根的深度是 $0$，它的儿子节点的深度为 $1$。

路径不必一定从根节点开始。

输入格式

第一行有两个整数 $n,s$，其中 $n$ 是树的节点数。
第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示节点 $i$ 的权值。
接下来的 $n-1$ 行，每行有两个个整数 $x$ 和 $y$，表示 $y$ 是 $x$ 的儿子。

输出格式

输出路径节点总和为 $s$ 的路径数量。

3 3
1 2 3
1 2
1 3

2

数据规模与约定

对于 $100\%$ 的数据，$1\le n\leq 10^5$，$1\leq s,a_i\leq 10^3$。