Loading...
Loading...
Loading...
A trekking club maps a hill as a tree of checkpoints. The base camp is the root, and the trail splits into at most two at each checkpoint. Each checkpoint has a height change in metres, which can be negative.
A route starts at the base camp and goes down to a checkpoint where the trail ends (a leaf). The guide wants routes whose height changes add up to exactly the target. Print how many routes do. An empty map has no routes.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. For example, 1 2 3 N 4 is root 1 with children 2 and 3, and 4 is the right child of 2. An empty tree is the single token N. The second line has one integer: the target.Example 1
Input
5 4 8 11 N 13 4 7 2 N N 5 1 22
Output
2
The routes 5 → 4 → 11 → 2 and 5 → 8 → 4 → 5 both add up to 22.
Example 2
Input
1 2 3 4
Output
1
Only 1 → 3 adds up to 4.
Try the problem first. Open one hint at a time.
Carry the target that is still left as you go down: subtract each value on the way.
Check the remaining target only at a leaf, where both children are missing.
The answer for a node is the answer for its left side plus the answer for its right side.
With negative values, a route can pass the target and come back to it, so never stop early.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor