Description
※This problem is modified from NTHUOJ 9024 - The Sum of a Tree Path
Given a binary tree, in which each node has an integer, determine whether there exists a tree path whose sum equal to the queried number.
A tree path is a path from the root to a leaf node. The sum of a tree path is the summation of numbers in each node on a tree path.
For example, in the tree shown below there are exactly three root-to-leaf paths. The sums of each path are 19, 8 and -6.
Given a binary tree, in which each node has an integer, determine whether there exists a tree path whose sum equal to the queried number.
A tree path is a path from the root to a leaf node. The sum of a tree path is the summation of numbers in each node on a tree path.
For example, in the tree shown below there are exactly three root-to-leaf paths. The sums of each path are 19, 8 and -6.
Input
The input consists of several test cases.
In each test case, the first line consists of three integers N and K and Q. N is total number of nodes (0<N<=1000). Each node has an index number id (1<=id<=N). K is index number of root, Q is queried number.
The following line consists of N integers (32bit int), where the i-th integer is the value of the node with index number i.
The next N lines will give you information of node relationship. Each line consists of three integers. The first integer is the index number of designated node A, and the second integer is the index number of left child of A, and the third integer is the index number of right child of A.(If A doesn't have left child or right child, then the corresponding child index number is 0.)
Output
For each test case, output “yes” or “no” in a new line to check whether the target does exist or not.