#1377
Frog Position After T Seconds
master · 1775 · lc hard +32 · verified · 38% accepted · 841 likes · top 17%
Description
An undirected tree has n vertices numbered 1 to n, with edges described by edges[i] = [ai, bi]. A frog starts at vertex 1. Each second, it jumps to a uniformly random unvisited neighbor; if none exist, it stays on its current vertex forever.
Return the probability that the frog is on vertex target after exactly t seconds. Answers within 10-5 of the exact value are accepted.
Example 1:
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and then jumping with 1/2 probability to vertex 4 after second 2. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.
Example 2:
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 0.3333333333333333
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1.
Code
1
2
3