750. Downward Paths That Add Up to t
A binary tree is given. Count the DOWNWARD paths whose values add up to exactly t.
A downward path is any sequence of nodes where each is the parent of the next. It need not start at the root and need not end at a leaf. A single node is a path of length one.
tree rooted at 4, children 2 and 6, then 1 3 5 7
t = 17 -> 1 the path 4, 6, 7
t = 6 -> 2
t = 4 -> 1
## Every downward path is a difference of two root-to-node totals
Let run(v) be the sum from the root down to v. For a path from an ancestor u down to v,
the total is
run(v) - run(parent of u)
So the path sums to t exactly when some ancestor position has
run = run(v) - t.
That is problem 286 again, "how many earlier prefixes equal this one minus the target", except the prefixes no longer lie along an array. They lie along the PATH FROM THE ROOT to the current node.
Recognising that the prefix-and-map technique works over any sequence, including one that only exists on a call stack, is the whole point of this problem.
## The map must describe the current path only
Walk the tree depth first, carrying the running root-to-node total and a map from total to how many times it has occurred ON THE CURRENT PATH.
visit(v, run):
run += value(v)
answer += counts[run - t]
counts[run] += 1
visit(left); visit(right)
counts[run] -= 1 <-- undo on the way back up
That last line is the problem. Without it the map accumulates totals from branches that are not ancestors of the current node, and paths get counted that do not exist as a single downward chain.
The error is invisible on a path-shaped tree, because there is only one branch and nothing to leak. It shows the moment a node has two children, which is why the sample tree is full.
## Seed the map with one zero
counts[0] = 1 before the walk stands for the empty prefix above the root, and it is what lets
a path STARTING at the root be counted. Without it every root-anchored path is lost.
## Values may be negative
A negative value means the running total is not increasing down a path, so there is no way to prune the search. Every node must be visited and the map is the only tool. Any method that assumes the total only grows is wrong here.
## Boundaries
A single node counts 1 when its value is t, and 0 otherwise. An all-zero tree with t = 0
counts every downward path.
## Overflow
100000 nodes of magnitude 10^9 give root-to-node totals of 10^14, so both the running
total and t need 64 bits.
The ANSWER needs them too, which is easy to miss because it is only a count. A chain of 100000
zero-valued nodes with t = 0 is a legal input, and every one of its downward paths qualifies,
so the count is 100000 * 100001 / 2 = 5000050000, about 5 * 10^9. An accumulator held in a
signed 32 bit integer wraps on that input while the running total beside it is perfectly fine.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `-10^9 ≤ each value ≤ 10^9` - `-10^14 ≤ t ≤ 10^14` - 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 one integer, the number of downward paths summing to t.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.