[JLOI2012] 树

题目描述

在这个问题中,给定一个值 $s$ 和一棵树。在树的每个节点有一个权值,第 $i$ 个点的权值为 $a_i$,问有多少条路径的节点权值总和为 $s$。路径中节点的深度必须是升序的。假设节点 $1$ 是根节点,根的深度是 $0$,它的儿子节点的深度为 $1$。路径不必一定从根节点开始。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3 3
1 2 3
1 2
1 3

输出样例 #1

2

说明

#### 数据规模与约定 - 对于 $100\%$ 的数据,保证 $1 \leq n \leq 10^5$,$1 \leq a_i, s \leq 10^3$。