Path Sum in Tree

You are given a tree with N nodes. Each node has an integer value associated with it. The tree is represented by its nodes and N-1 edges. The root of the tree is node 1.

Your task is to determine whether there exists a path starting from the root such that the sum of the node values along that path equals S.

A path is defined as a sequence of nodes connected by edges, and you cannot revisit nodes. If such a path exists, print True; otherwise, print False.

The equation for the target sum can be written in LaTeX as: \(\sum_{i \in path} a_i = S\), where \(a_i\) represents the value of node \(i\).

inputFormat

The input is given via standard input (stdin) in the following format:

N S
v1 v2 ... vN
u1 v1
u2 v2
... 
u(N-1) v(N-1)

Where:

• N is the number of nodes.
• S is the target sum.
• The second line contains N integers, representing the values of the nodes from 1 to N.
• Each of the next N-1 lines contains two integers representing an edge between two nodes.

outputFormat

Output a single line to standard output (stdout) containing either True or False. It should be True if there is a path starting from the root with a sum equal to S, and False otherwise.

## sample

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

True