Tree Path Sum Prefix Counts

Problem

Count the unordered pairs of distinct nodes in a tree whose node-value sum equals target.

For every start node, explore the tree with a stack carrying the running path sum and count endpoints greater than the start whose sum matches. values[i] is the value of node i. edges is a list of [u, v] pairs.

Hint

Paths in a tree are unique, so a DFS from each start enumerates them all.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3]],[1,2,3,4],5]

expected: 1

case 2

in: [3,[[0,1],[1,2]],[1,1,1],2]

expected: 2

case 3

in: [3,[[0,1],[1,2]],[1,2,3],3]

expected: 1

Starter codePython

def tree_path_sum_counts(n, edges, values, target):
    # Your code here
    pass

3 test cases · run your code against them in the editor