Description

In this problem, you are given a value $s$ and a tree. Each node has a weight; the $i$-th node has weight $a_i$. Count how many paths have a total sum of node weights equal to $s$. The depths of nodes along a path must be in strictly increasing order. Assume node $1$ is the root, its depth is $0$, and the depth of each of its children is $1$. A path does not have to start at the root.

Input Format

The first line contains two integers $n$ and $s$, where $n$ is the number of nodes in the tree.

The second line contains $n$ integers; the $i$-th integer $a_i$ denotes the weight of node $i$.

The next $n - 1$ lines each contain two integers $x$ and $y$, indicating that $y$ is a child of $x$.

Output Format

Output the number of paths whose total node weight equals $s$.

3 3
1 2 3
1 2
1 3

2

Hint

Constraints

• For $100\%$ of the testdata, it holds that $1 \leq n \leq 10^5$, $1 \leq a_i, s \leq 10^3$.

Translated by ChatGPT 5