Rooted Tree Polynomial Hash

Problem

Compute a polynomial hash of a tree rooted at root.

With children of a node sorted by increasing hash and k the number of children, h(v) = ((1 + sum h(c_i) * base^(i+1)) * (k + 1)) mod mod for i starting at 1, using base 131 and mod 1000000007; the arity factor keeps a chain from hashing like a star. Process nodes in reverse BFS order. edges is a list of [u, v] pairs. Return the hash of the root.

Hint

Sorting sibling hashes before mixing makes the value independent of adjacency order.

Test cases

case 1

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

expected: 18122542

case 2

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

expected: 9061536

case 3

in: [1,[],0]

expected: 1

case 4

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

expected: 561079877

Starter codePython

def rooted_tree_hash(n, edges, root):
    # Your code here
    pass

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