Difference Array on Tree

Problem

Count how many given paths cover each node of a tree using the standard difference trick.

For each path u-v add 1 at u and v, subtract 1 at their LCA, and subtract 1 at the LCA's parent; then accumulate counts upward in reverse BFS order. Return the coverage count of every node. edges is a list of [u, v] pairs and paths is a list of endpoint pairs; the tree is rooted at 0.

Hint

The four-point update makes each path contribute exactly on its nodes.

Test cases

case 1

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

expected: [1,2,2,1]

case 2

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

expected: [2,2,1,1]

case 3

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

expected: [2,2,1]

Starter codePython

def tree_difference_counts(n, edges, paths):
    # Your code here
    pass

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