Algorithms and Data Structures

# Path Sum From Root

You are given a tree with `n` nodes, where the `i`-th node has an assigned value (). Your task is to find the number of paths in the tree that start from the root node and have a sum equal to a given value `s`.

#### Input

The first line contains two integers separated by a space: `n` and `s` (), representing the number of nodes in the tree and the target sum respectively. The second line contains `n` space-separated integers through (), representing the values assigned to each node in the tree. The following `n-1` lines represent the edges of the tree, with each line containing two space-separated integers `a` and `b` (1 ≤ a, b ≤ n), indicating an edge between nodes `a` and `b`. It is guaranteed that the given edges form a tree.

#### Output

Print a single integer, representing the number of paths in the tree that start from the root node and have a sum equal to the given value `s`.

#### Examples

 Input Output 5 6 1 2 3 4 5 1 2 2 3 1 5 5 4 2

#### Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB