Path Sum in a Tree

Given a tree with n nodes and a target value \(s\), each node \(i\) has an integer weight \(a_i\). The tree is rooted at node 1 with depth 0, and the depth of each child is one more than its parent's depth. A path is defined as a sequence of nodes where the depth is strictly increasing (i.e. every node in the path is a descendant of the previous one). The path can start at any node, not necessarily the root. Your task is to count the number of paths whose sum of node weights is exactly \(s\).

Input Format: The first line contains two integers \(n\) and \(s\). The second line contains \(n\) integers \(a_1, a_2, ..., a_n\), representing the weights of the nodes. Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) indicating there is an edge between nodes \(u\) and \(v\>.

Output Format: Output a single integer representing the number of paths with the sum of weights equal to \(s\).

inputFormat

The input begins with two integers \(n\) and \(s\) (n is the number of nodes, and \(s\) is the target sum). The second line contains \(n\) integers representing the weights \(a_1, a_2, \ldots, a_n\) of each node. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), meaning that there is an edge between node \(u\) and node \(v\). Node 1 is the root and has depth 0.

outputFormat

Output a single integer representing the total number of paths where the sum of the weights is exactly \(s\). A path is valid if the depths of its nodes are strictly increasing.

sample

5 3
1 2 1 1 1
1 2
1 3
2 4
2 5

3