345. Is There a Path Adding to T
Core1000 ms256 MBSolved by 0%
Print Yes if some root-to-leaf path has values totalling exactly t, and
No otherwise.
The path must run from the root all the way to a LEAF. A partial path that
happens to reach t part way down does not count, and neither does a path
between two nodes that avoids the root.
Carry the running total down and compare it with t only on arrival at a leaf.
Values may be negative, so you cannot abandon a branch merely because the total
has already passed t.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000000000 ≤ t ≤ 1000000000000000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains two integers n and t.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root.
Output
Print Yes or No on one line.
Input7 17
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
OutputYes
Noteis 4 + 6 + 7 down the right branch
Input7 5
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
OutputNo
Notereaches 5 part way down but not at any leaf
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution