Frog Position After T Seconds
Given an undirected tree consisting of n vertices numbered from 1 to n, a frog starts jumping from vertex 1.
In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog cannot jump back to a visited vertex. If the frog can jump to several vertices, it chooses one of them randomly with the same probability. Otherwise, when the frog cannot jump to any unvisited vertex, it jumps forever on the same vertex.
The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means there is an edge connecting vertices ai and bi.
Return the probability that after t seconds the frog is on vertex target. Answers within 10^-5 of the actual answer will be accepted.
Example 1
Input
n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4Output
0.16666666666666666The frog moves from vertex 1 to vertex 2 with probability 1/3 after the first second, then from vertex 2 to vertex 4 with probability 1/2 after the second second, so the probability is 1/6.
Example 2
Input
n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7Output
0.3333333333333333The frog starts at vertex 1 and jumps to vertex 7 after one second with probability 1/3.
Constraints
- 1 <= n <= 100
- edges.length == n - 1
- edges[i].length == 2
- 1 <= ai, bi <= n
- 1 <= t <= 50
- 1 <= target <= n