Hitting Time Symmetric Formula

Problem

Compute the expected hitting time h(u, v) of the simple random walk on a tree with n nodes.

The tree formula is h(u, v) = dist(u, v) + 2 * sum over edges e on the u-to-v path of the number of edges in the component containing u after removing e. Root the tree at u and use subtree sizes. edges is a list of [u, v] pairs; return an integer.

Hint

For edges closer to v the u-side component contains more of the tree's edges.

Test cases

case 1

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

expected: 4

case 2

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

expected: 5

case 3

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

expected: 6

case 4

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

expected: 1

case 5

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

expected: 16

Starter codePython

def hitting_time_tree(n, edges, u, v):
    # Your code here
    pass

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