Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from the vertex 1. In one second, the frog jumps from its current vertex to another unvisited 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. 
The edges of the undirected tree are given in the array edges, where edges[i] = [fromi, toi] means that exists an edge connecting directly the vertices fromi and toi.
Return the probability that after t seconds the frog is on the vertex target.
 
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. 

Example 3:
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
Output: 0.16666666666666666

 
Constraints:

1 <= n <= 100
edges.length == n-1
edges[i].length == 2
1 <= edges[i][0], edges[i][1] <= n
1 <= t <= 50
1 <= target <= n
Answers within 10^-5 of the actual value will be accepted as correct.

Difficulty: interview

Starter code:

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        

Solutions:
class Solution:
  def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
    tree = dict()
    for i, j in edges:
      if i > j: i, j = j, i
      tree.setdefault(i - 1, []).append(j - 1)

    queue, time = [(0, 1)], 0  # node-prob
    while queue and time <= t:  # bfs 
      tmp = []
      for node, prob in queue:
        if node == target - 1: return 0 if time < t and node in tree else prob
        for n in tree.get(node, []): tmp.append((n, prob / len(tree[node])))
      queue, time = tmp, time + 1
    return 0 


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        to_edges = defaultdict(list)
        for [so, ta] in edges:
            to_edges[so].append(ta)
            to_edges[ta].append(so)
        to_edges[1].append(1)

        queue = deque([(1, 0, 1)])
        visited = {1}
        while queue:
            node, time, frac = queue.popleft()
            if node == target:
                if time == t or (time<t and len(to_edges[node]) == 1):
                    return 1/frac
            if time > t:
                return 0
            for nei in to_edges[node]:
                if nei not in visited:
                    queue.append((nei, time+1, frac*(len(to_edges[node])-1)))
                    visited.add(nei)

        return 0

from collections import deque

class Solution:
  def frogPosition(self, n: int, edges_inp: List[List[int]], t: int, target: int) -> float:
    edges = [ [] for _ in range(n+1) ]
    for v0, v1 in edges_inp:
      edges[v0].append( v1 )
      edges[v1].append( v0 )
    # determine at what step and what probability 
    visited = [0 for _ in range(n+1)]
    q = deque()   # format (vertice, step, probability)
    visited[1] = 1
    q.append( (1,0,1.0) )
    print(edges)
    while q:
      node, step, prob = q.popleft()
      print(node, step, prob)
      if step>t:
        return 0
      sub = 0 if node==1 else 1
      if node == target:
        if step == t or len(edges[node]) == sub:
          return prob
      if len(edges[node]) > sub:
        prob_next = prob / (len(edges[node])-sub)
        for node_next in edges[node]:
          if visited[node_next]:
            continue
          print(\">\", node, node_next, step+1, prob_next)
          q.append( (node_next, step+1, prob_next) )
          visited[node_next] = 1
    return 0
  

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        tree = dict()
        for i,j in edges:
            if i>j:
                i,j = j,i
            tree.setdefault(i-1,[]).append(j-1)
        q,time = [(0,1)],0
        while q and time <= t:
            tmp = []
            for node,prob in q:
                if node == target-1:
                    return 0 if time <t and node in tree else prob
                for n in tree.get(node,[]):
                    tmp.append((n,prob/len(tree[node])))
            q,time = tmp,time+1
        return 0
    
    



class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        ans= None
        graph= defaultdict(set)
        for x,y in edges:
            graph[x].add(y)
            graph[y].add(x)


        vis=set([1])

        def  dfs(root,prev_prob,t):
            nonlocal ans
            if  t < 0 : return 
            can = graph[root] - vis

            if root== target:
                ans = prev_prob if not can or t== 0 else 0
                return 
            for x in can:
                if x not in vis:
                    vis.add(x)
                    dfs(x,prev_prob * 1.0 / len(can),t-1)
                if ans is not None : return
        dfs(1,1,t)
        return 0 if ans is None else ans

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
            
        seen = set([1])
        
        queue = collections.deque([(1, 1)])
        
        while t > 0:
            size = len(queue)
            for _ in range(size):
                f, prob = queue.popleft()
                length = 0
                for nb in graph[f]:
                    if nb not in seen:
                        length += 1
                        
                if length == 0:
                    queue.append((f, prob))
                else:
                    for nb in graph[f]:
                        if nb not in seen:
                            seen.add(nb)
                            queue.append((nb, prob / length))
                            
            t -= 1
            
        res = 0
        for node, prob in queue:
            if node == target:
                res += prob
                
        return res

                        
                


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        if n == 1:
            return 1.0

        graph = collections.defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        q = collections.deque()
        q.append((1, 1.0))
        visited = set()
        
        self.target = target
        return self.dfs(graph, 1, t, visited)
    
    def dfs(self, graph, i, t, visited):
        if t == 0 or (i != 1 and len(graph[i]) == 1):
            if i == self.target:
                return 1
            return 0

        result = 0
        visited.add(i)
        for j in graph[i]:
            if j not in visited:
                result += self.dfs(graph, j, t - 1, visited)
        
        if i == 1:
            return result / len(graph[i])
        else:
            return result / (len(graph[i]) - 1)

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = {i:set() for i in range(1, n+1)}
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
        
        queue = collections.deque([(1, 1)])
        
        seen = set([1])
        
        level = 0
        
        while level < t:
            size = len(queue)
            for _ in range(size):
                f, prob = queue.popleft()
                nextCnt = 0
                for nb in graph[f]:
                    if nb not in seen:
                        nextCnt += 1
                if nextCnt == 0:
                    queue.append((f, prob))
                    
                else:
                    for nb in graph[f]:
                        if nb not in seen:
                            queue.append((nb, prob / nextCnt))
                            seen.add(nb)
            level += 1
                            
        ans = 0
        for node, prob in queue:
            if node == target:
                ans += prob
                
        return ans


import queue 
from collections import defaultdict
class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        q = queue.Queue()
        graph = defaultdict(list)
        degree = [0] * (n+1)
        for f, end in edges:
            graph[f].append(end)
            graph[end].append(f)
            degree[end] += 1
        start = 1
        # for ind, val in enumerate(degree):
        #     if val == 0:
        #         start = ind 
        visited = set()
        
        q.put([start, 1, 1]) # node, level (t is # of level), prob
        visited.add(start)
        res = 0 
        qt = 0
        
        p = [0] * (n+1)
        p[1] = 1.0
        while t and not q.empty():
            qsize = q.qsize()
            for _ in range(qsize):
                node, level, prob = q.get()
                size = 0
                for nei in graph[node]:
                    if nei not in visited:
                        size += 1
                for nei in graph[node]:
                    if nei not in visited:
                        visited.add(nei)
                        q.put([nei, level+1, prob*(1/size)])
                        p[nei] = p[node]/size
                if size > 0:
                    p[node] = 0 
            t -= 1
        return p[target]

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = collections.defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        q = collections.deque()
        q.append((1, 1.0))
        visited = set()
        visited.add(1)
        
        step = 0
        while q and step <= t:
            size = len(q)
            for _ in range(size):
                i, prob = q.popleft()
                if step == t and i == target:
                    return prob

                count = 0
                if i == 1:
                    count = len(graph[i])
                else:
                    count = len(graph[i]) - 1
                
                if count == 0:
                    q.append((i, prob))
                    continue
                
                for neighbor in graph[i]:
                    if neighbor not in visited:
                        q.append((neighbor, prob / count))
                        visited.add(neighbor)
                
            step += 1
        
        return 0.0

from collections import defaultdict
import queue

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        d = defaultdict(set)
        visited = set()
        for edge in edges:
            d[edge[0]].add(edge[1])
            d[edge[1]].add(edge[0])
        q = queue.Queue()
        q.put((1, 0, 1.0))
        visited.add(1)
        goal = {}
        
        while not q.empty():
            cur, time, p = q.get()
            if time > t:
                if target in goal:
                    return goal[target]
                return 0.0
            if cur == target and time == t:
                return p
            c = 0
            for adj in d[cur]:
                if adj not in visited:
                    c += 1
            if c == 0:
                goal[cur] = p
                continue
            for adj in d[cur]:
                if adj not in visited:
                    q.put((adj, time + 1, p / c))
                    visited.add(adj)
        
        if target in goal:
            return goal[target]
        return 0.0


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        
        
        table={}
        for i in range(1,n+1):
            table[i]=[]
        for i in range(len(edges)):
            table[edges[i][0]].append(edges[i][1])
            table[edges[i][1]].append(edges[i][0])
        
        
        #print(table)
        
        self.res=0
        def DFS(current_node,p,visited,time):
            #print(current_node,p,visited,time)
            if time == t:
                if current_node == target:
                    self.res += p
            elif time <t:
                temp=0
                for node in table[current_node]:
                    if node not in visited:
                        temp +=1
                if temp >0:
                    for node in table[current_node]:
                        if node not in visited:
                            temp_visited = visited[:]
                            temp_visited.append(node)
                            DFS(node,p*1/temp,temp_visited,time+1)
                elif temp ==0:
                    DFS(current_node,p,visited,time+1)
        
        DFS(1,1,[1],0)
        
        return self.res
                


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        if not edges:
            return target == 1
        G = defaultdict(list)
        for s, e in edges:
            G[s].append(e)
            G[e].append(s)
        def dfs(idx, fr, p, step):
            if step > t:
                return 0
            if idx == target:
                if step == t or (idx != 1 and len(G[idx]) == 1 or idx == 1 and not G[idx]):
                    return p
                else:
                    return 0
            if idx != 1 and len(G[idx]) == 1:
                return 0
            for nb in G[idx]:
                if nb == fr:
                    continue
                ret = dfs(nb, idx, p / ((len(G[idx]) - 1) if idx != 1 else len(G[idx])), step + 1)
                if ret:
                    return ret
            return 0
        return dfs(1, 0, 1, 0)


def oneJump( edges, visited, target, cur, t):
    
    if t == 0:
        return 0
    
    if t == 1 and cur == target:
        return 1
    
    nxt = []
    visited[cur] = 1
    
    for i in edges:
        
        if i[0] == cur and visited[i[1]] == 0:
            nxt.append(i[1])
        
        elif i[1] == cur and visited[i[0]] == 0:
            nxt.append(i[0])
    
    if len(nxt) == 0: 
        if cur == target:
            return 1
        else:
            return 0
    
    for i in nxt:
        
        n = oneJump( edges, visited, target, i, t-1)
        if n != 0:
            return (1/len(nxt)) * n
    
    return 0         
    
class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        points = [ i for i in range(1,n+1)]
        vis = [0 for i in range(n)]
        
        visited = dict(zip(points, vis))
        return oneJump( edges, visited, target, 1, t+1)

from collections import defaultdict, deque

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        nei = collections.defaultdict(set)
        for a, b in edges:
            nei[a].add(b)
            nei[b].add(a)
            
        dp = collections.deque([(1, 1, 0)]) # state: leaf_id, possibility, timestamp
        visited = set()
        
        while dp:
            leaf, p, curr = dp.popleft()
            visited.add(leaf)
            
            if curr >= t:
                if leaf == target: return p
                continue
            
            neighbors = nei[leaf] - visited
            for n in neighbors or [leaf]:
                dp += (n, p / (len(neighbors) or 1), curr + 1),
        return 0.


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
#         if n == 1: return 1.0
#         G = [[] for i in range(n + 1)]
#         for i, j in edges:
#             G[i].append(j)
#             G[j].append(i)
#         seen = [0] * (n + 1)

#         def dfs(i, t):
#             if i != 1 and len(G[i]) == 1 or t == 0:
#                 return i == target
#             seen[i] = 1
#             res = sum(dfs(j, t - 1) for j in G[i] if not seen[j])
#             return res * 1.0 / (len(G[i]) - (i != 1))
#         return dfs(1, t)

        nei = collections.defaultdict(set)
        for a, b in edges:
            nei[a].add(b)
            nei[b].add(a)
            
        visited, res = set(), 0.
        def dfs(leaf_id, p, time):
            nonlocal res
            if time >= t:
                if leaf_id == target: 
                    res = p
                return
            visited.add(leaf_id)
            neighbors = nei[leaf_id] - visited
            for n in neighbors or [leaf_id]:
                dfs(n, p / (len(neighbors) or 1), time + 1)
        dfs(1, 1, 0)
        return res          


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
#         if n == 1: return 1.0
#         G = [[] for i in range(n + 1)]
#         for i, j in edges:
#             G[i].append(j)
#             G[j].append(i)
#         seen = [0] * (n + 1)

#         def dfs(i, t):
#             if i != 1 and len(G[i]) == 1 or t == 0:
#                 return i == target
#             seen[i] = 1
#             res = sum(dfs(j, t - 1) for j in G[i] if not seen[j])
#             return res * 1.0 / (len(G[i]) - (i != 1))
#         return dfs(1, t)

        nei = collections.defaultdict(set)
        for a, b in edges:
            nei[a].add(b)
            nei[b].add(a)
            
        visited, res = set(), 0.
        def dfs(leaf_id, p, time):
            nonlocal res
            if time >= t:
                if leaf_id == target: res = p
                return
            visited.add(leaf_id)
            neighbors = nei[leaf_id] - visited
            for n in neighbors or [leaf_id]:
                dfs(n, p / (len(neighbors) or 1), time + 1)
        dfs(1, 1, 0)
        return res          


from collections import defaultdict
class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        self.prob = 0
        mp = defaultdict(set)
        for edge in edges:
            mp[edge[0]].add(edge[1])
            mp[edge[1]].add(edge[0])
        visited = set()
        visited.add(1)
        
        def backtrack(pos: int, nowprob: float, currtime: int, visited: Set[int]):
            if currtime == t:
                if pos == target:
                    self.prob += nowprob
                return
            total_visited = 0
            for edge in mp[pos]:
                if edge in visited:
                    total_visited += 1
            div = len(mp[pos]) - total_visited
            if div == 0:
                if pos == target:
                    self.prob += nowprob
                return
            for edge in mp[pos]:
                if edge not in visited:
                    visited.add(edge)
                    backtrack(edge, nowprob/div, currtime+1, visited)
                    visited.remove(edge)
        
            
        backtrack(1, 1, 0, visited)
        return self.prob
                
            


class Solution:
    def frogPosition(self, n: int, edges, t: int, target: int) -> float:
        nei = collections.defaultdict(set)
        for i, j in edges:
            nei[i].add(j)
            nei[j].add(i)
            
        dp = collections.deque([(1, 1, 0)]) # state: leaf_id, possibility, timestamp
        visited = set()
        
        while dp:
            leaf, p, curr = dp.popleft()
            visited.add(leaf)
            
            if curr >= t:
                if leaf == target: return p
                continue
            
            neighbors = nei[leaf] - visited
            for n in neighbors or [leaf]:
                dp += (n, p / (len(neighbors) or 1), curr + 1),
        return 0.


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = collections.defaultdict(list)
        
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
            
        
        q = [(1, 1, 0)]
        seen = set()
        
        while q:
            curr, p, time = q.pop(0)
            if time >= t:
                if curr == target:
                    return p
                continue 
                
            seen.add(curr)
            s = 0
            for nei in graph[curr]:
                if nei not in seen:
                    s += 1
            if s:
                for nei in graph[curr] :
                    if nei not in seen:
                        q.append((nei, p / s, time + 1))
            else:
                q.append((curr, p, time + 1))
                
        return 0. 


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        neigh = {}
        for e in edges:
            neigh[e[0]] = neigh.get(e[0],[])+[e[1]]
            neigh[e[1]] = neigh.get(e[1],[])+[e[0]]
        front = [1]
        steps = 0
        p = { i:0 for i in range(1,n+1)}
        p[1] = 1
        visited = set([1])
        for steps in range(t):
            q = {}
            for i in p:
                if p[i]!=0:
                    if i==1 and  len(neigh.get(i,[]))==0:
                        q[i] = p[i]
                    elif  len(neigh.get(i,[]))<=1 and i!=1:
                        q[i] = p[i]
                    else:
                        if i == 1:
                            nn = len(neigh.get(i,[]))
                        else:
                            nn =len(neigh.get(i,[]))-1
#                        print(i,nn)
                        for j in neigh.get(i,[]):
                            if not j in visited:
                                q[j] = p[i]/nn
                                visited.add(j)
            p = {i:q.get(i,0) for i in range(1,n+1)}
#            print(steps,p)
#        print(neigh)
        return(p.get(target,0))           
            


from collections import defaultdict, deque

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = defaultdict(set)
        for src, dest in edges:
            graph[src].add(dest)
            graph[dest].add(src)
        
        q = deque([[1, 1.0, 0]])
        visited = set()
        while q:
            node, prob, time_step = q.popleft()
            visited.add(node)
            
            if time_step >= t:
                if node == target:
                    return prob
                continue
            
            neighbors = graph[node] - visited
            nxt_prob = prob / max(len(neighbors), 1)
            for child in neighbors or [node]:
                q.append((child, nxt_prob, time_step+1))
        
        return 0.0


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        tree = dict()
        for i, j in edges: 
            if i > j: i, j = j, i
            tree.setdefault(i-1, []).append(j-1)
        
        queue, time = [(0, 1)], 0 #node-prob
        while queue and time <= t: #bfs 
            tmp = []
            for node, prob in queue: 
                if node == target-1: return 0 if time < t and node in tree else prob
                for n in tree.get(node, []): tmp.append((n, prob/len(tree[node])))
            queue, time = tmp, time+1
        return 0 


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = {}
        for x, y in edges:
            graph[x] = graph.get(x, set())
            graph[x].add(y)
            graph[y] = graph.get(y, set())
            graph[y].add(x)
            
        queue = [(1, 0, 1)]
        visited = set([1])
        while queue:
            
            if queue[0][1] == t:
                break
            node, time, p = queue.pop(0)
            
            neis = [x for x in graph.get(node, []) if x not in visited]
            size =len(neis)
            if neis:
                for nei in neis:
                    queue.append([nei, time + 1, p*1/size])
                    visited.add(nei)
            else:
                 queue.append((node,time + 1, p*1))
        while queue:
            node,t, prob = queue.pop(0)
            if node == target:
                return prob
        return 0

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        visited=[False for i in range(n+1)]
        visited[0]=True
        visited[n]=True
        prb=[0 for i in range(n)]
        prb[0]=1
        edgelists=[[] for i in range(n)]
        for i in edges:
            x=i[0]-1
            y=i[1]-1
            edgelists[x].append(y)
            edgelists[y].append(x)
        edgelists[0].append(n)
        curr=[0]
        for _ in range(t):
            nex=[]
            print(curr)
            for i in curr:
                occ=False
                for j in edgelists[i]:
                    if(visited[j]==False):
                        occ=True
                        nex.append(j)
                        prb[j]=prb[i]/(len(edgelists[i])-1)
                        visited[j]=True
                if(occ):
                    prb[i]=0
            curr=nex
        print(prb)
        return prb[target-1]
                
            
            
            


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        if n == 1: 
            return 1.0
        
        G = collections.defaultdict(list)
        for i, j in edges:
            G[i].append(j)
            G[j].append(i)
            
        seen = set()
        
        # it's a tree, so the frog can not go back to parent
        def probability(idx, t):
            if t == 0:
                return idx == target
            if idx != 1 and len(G[idx]) == 1: # if the frog is stuck at this vertex
                return idx == target
            seen.add(idx)
            res, count = 0, 0
            for j in G[idx]:
                if not j in seen:
                    res += probability(j, t - 1) 
                    count += 1
            return res / count
        
        return probability(1, t)

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        if n == 1: 
            return 1.0
        
        G = collections.defaultdict(list)
        for i, j in edges:
            G[i].append(j)
            G[j].append(i)
            
        seen = set()
        
        # it's a tree, so the frog can not go back to parent
        def probability(idx, t):
            if t == 0:
                return idx == target
            if idx != 1 and len(G[idx]) == 1: # if the frog is stuck at this vertex
                return idx == target
            seen.add(idx)
            res = sum(
                probability(j, t - 1) 
                for j in G[idx] 
                if not j in seen
            )
            return res * 1.0 / (len(G[idx]) - (idx != 1))
        
        return probability(1, t)

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        neighbors = defaultdict(list)
        for u, v in edges:
            neighbors[u].append(v)
            neighbors[v].append(u)
        
        def dfs(u, tt, r):
            if tt > t or u in visited:
                return 0
            if u == target:
                if len(neighbors[u]) > (0 if r else 1) and tt < t:
                    return 0
                else:
                    return 1
            visited.add(u)
            m = 0
            for v in neighbors[u]:
                m = max(m, dfs(v, tt+1, False))
            visited.remove(u)
            if r and neighbors[u]:
                return m / len(neighbors[u])
            elif not r and len(neighbors[u]) > 1:
                return m / (len(neighbors[u]) - 1)
            else:
                return 0
        
        visited = set()
        return dfs(1, 0, True)
            


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = collections.defaultdict(set)
        for s, e in edges:
            graph[s].add(e)
            graph[e].add(s)
        
        def dfs(prev_node: int, seconds_left: int, visited: Set[int]):
            if seconds_left == 0 or prev_node not in graph:
                return int(prev_node == target)
            
            probability = 0
            n_next_node = 0
            for next_node in graph[prev_node]:
                if next_node not in visited:
                    probability += dfs(next_node, seconds_left-1, set(list(visited) + [prev_node]))
                    n_next_node += 1
            if n_next_node == 0:
                return int(prev_node == target)
            if probability > 0:
                probability /= n_next_node
            return probability
            
        
        return dfs(prev_node=1, seconds_left=t, visited=())

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        if n == 1: return 1.0
        graph = [[] for i in range(n + 1)]
        for i, j in edges:
            graph[i] += j,
            graph[j] += i,
        visited = [0] * (n + 1)

        def dfs(i, t):
            if i != 1 and len(graph[i]) == 1 or t == 0: return i == target
            visited[i] = 1
            res = sum(dfs(j, t - 1) for j in graph[i] if not visited[j])
            return res * 1.0 / (len(graph[i]) - (i != 1))
        return dfs(1, t)

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        
 
        tree = {}

        def add_edge(parent, child):
            children = tree.get(parent, [])
            children.append(child)
            tree[parent] = children
        for [a, b] in edges:
            add_edge(a,b)
            add_edge(b,a)

        if n == 1:
            return 1.0

        result = 1.0 if target == 1 else 0.0
        # is list of `(node, probability)` pairs
        state = [(1, 1.0)]
        visited = set([1])
        for i in range(t):
            new_state = []
            for node, probability in state:
                children = [child for child in tree[node] if child not in visited]
                if len(children) == 0:
                    if node == target:
                        return probability
                    # new_state.append( (node, probability) )
                    continue
                if node == target:
                    return 0
                visited.add(node)
                for child in tree[node]:
                    new_probability = probability * 1/len(children)
                    if child == target:
                        result = new_probability
                    new_state.append( (child, new_probability) )
            state = new_state

        return result