Path Sum in a Binary Tree

Given a binary tree and a target integer ( S ), determine if there exists a downward path starting from any node such that the sum of the node values along the path equals ( S ). A valid path is a sequence of nodes where each consecutive node is a child of its predecessor. The path can consist of a single node.

For example, consider the following binary tree:
(3)
(/ \ \ \ \ \ \ \ \ \backslash)
(4) (2)
(/ \ \ \ \ \ \ \backslash)
(-3) (5) (6) (-2)

If ( S = 6 ), one valid path is the node with value 6 (by itself), yielding the sum 6.

inputFormat

The input is read from standard input.

The first line contains an integer ( n ) -- the number of nodes in the binary tree.
The second line contains ( n ) space-separated integers representing the values of the nodes (indexed from 1).
Each of the next ( n-1 ) lines contains two integers ( u ) and ( v ) representing an edge from node ( u ) to node ( v ). It is guaranteed that these edges form a binary tree. The children are assigned in the order they are provided: if the left child is not assigned, the first encountered child becomes the left child; otherwise, the next child becomes the right child.
The last line contains the integer ( S ), the target sum.

outputFormat

Print to standard output a single line: either True if there exists at least one downward path whose sum equals ( S ), or False if no such path exists.## sample

7
3 4 2 -3 5 6 -2
1 2
1 3
2 4
2 5
3 6
3 7
6

True