<p>Given an undirected tree consisting of <code>n</code> vertices numbered from <code>1</code> to <code>n</code>. A frog starts jumping from <strong>vertex 1</strong>. In one second, the frog jumps from its current vertex to another <strong>unvisited</strong> vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices, it jumps randomly to one of them with the same probability. Otherwise, when the frog can not jump to any unvisited vertex, it jumps forever on the same vertex.</p>

<p>The edges of the undirected tree are given in the array <code>edges</code>, where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> means that exists an edge connecting the vertices <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>.</p>

<p><em>Return the probability that after <code>t</code> seconds the frog is on the vertex <code>target</code>. </em>Answers within <code>10<sup>-5</sup></code> of the actual answer will be accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/21/frog1.jpg" style="width: 338px; height: 304px;" />
<pre>
<strong>Input:</strong> n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
<strong>Output:</strong> 0.16666666666666666 
<strong>Explanation:</strong> The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after <strong>second 1</strong> and then jumping with 1/2 probability to vertex 4 after <strong>second 2</strong>. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666. 
</pre>

<p><strong class="example">Example 2:</strong></p>
<strong><img alt="" src="https://assets.leetcode.com/uploads/2021/12/21/frog2.jpg" style="width: 304px; height: 304px;" /></strong>

<pre>
<strong>Input:</strong> n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
<strong>Output:</strong> 0.3333333333333333
<strong>Explanation: </strong>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 <strong>second 1</strong>. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n</code></li>
	<li><code>1 &lt;= t &lt;= 50</code></li>
	<li><code>1 &lt;= target &lt;= n</code></li>
</ul>

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        # Edge case
        if n == 1: return 1
        # Build tree edges
        E = self.get_edges(edges)        
        # Compute distances and parents of tree rooted at 1
        dists, parents = self.bfs(1, E)
        # Get distance of target
        dist = dists[target]
        # Get path from target to root
        path = self.backtrack(target, parents)
        # Target is too far away or is root on non-trivial tree
        if dist > t or target == 1: return 0
        # Target is closer than t steps away and not leaf
        if dist < t and len(E[target]) > 1: return 0
        # Otherwise, target is either exactly t steps away, or 
        # at most t steps away and is a leaf
        # Get path from target to root, excluding target
        path = self.backtrack(target, parents)
        # All vertices along the way have one "incoming" edge
        weights = [len(E[v])-1 for v in path]
        # Apart from the root
        weights[-1] += 1
        res = 1
        for w in weights: res /= w
        return res

    # Construct tree from edges list
    def get_edges(self, edges):
        E = defaultdict(list)
        for u, v in edges:
            E[u].append(v)
            E[v].append(u)
        return E

    # Get path from target to root, excluding target
    def backtrack(self, target, parents):
        v = parents[target]
        res = []
        while v != None:
            res.append(v)
            v = parents[v]
        return res

    # Compute distance and parents from v to all nodes using BFS
    def bfs(self, root, E):
        seen = {root}
        Q = deque([(root, 0)])
        dists = {root: 0}
        parents = {root: None}
        while Q:
            v, d = Q.popleft()
            dists[v] = d
            for u in E[v]:
                if u not in seen:
                    parents[u] = v
                    seen.add(u)
                    Q.append((u, d+1))
        return dists, parents
93