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 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] = [ai, bi] means that exists an edge connecting the vertices ai and bi.

Return the probability that after t seconds the frog is on the vertex target. Answers within 10-5 of the actual answer will be accepted.

&nbsp;
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. 


&nbsp;
Constraints:


	1 &lt;= n &lt;= 100
	edges.length == n - 1
	edges[i].length == 2
	1 &lt;= ai, bi &lt;= n
	1 &lt;= t &lt;= 50
	1 &lt;= target &lt;= n


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        adj = [[] for i in range(n)]
        for u,v in edges:
            adj[u-1].append(v-1)
            adj[v-1].append(u-1)
        def f(u,p,tt):
            if(u==target-1): return tt==0 or len(adj[u])==(p>=0)
            if(tt==0): return 0
            res = 0
            for v in adj[u]:
                if(p==v): continue
                res = max(res,(1/(len(adj[u])-(p!=-1)))*f(v,u,tt-1))
            return res
        return f(0,-1,t)
            
            
        
class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
       
        List<List<Integer>> graph=new ArrayList<>();
        for(int i=0;i<=n;i++) graph.add(new ArrayList<>());
        
          for(int i=0;i<edges.length;i++) {
         
           graph.get(edges[i][0]).add(edges[i][1]);
           graph.get(edges[i][1]).add(edges[i][0]);
          
      }
        boolean[] vis=new boolean[n+1];
        return Sol(graph,1, t, target,vis);
        
    }
    public double Sol(List<List<Integer>> graph,int ver,int t,int tar,boolean[] vis){
        
         int count=0;
        for(Integer child:graph.get(ver)){
            if(!vis[child]) count++;
        }
        
        
        vis[ver]=true;
        if(t<0) return 0;
        
        if(ver==tar){
            if(count==0 || t==0) return 1.0;
         }
        
        if(graph.get(ver).size()==0) return 0;
        
        double ans=0.0;
        
       
        for(Integer child:graph.get(ver)){

           // System.out.println(child);
            if(!vis[child])
            ans+=(double)(1.0/count)*Sol(graph,child,t-1,tar,vis);
        }
       // System.out.println(ans);
        vis[ver]=false;
        return ans;
    }
}
class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        unordered_map<int, vector<int>> adjList;
        for(const auto& edge : edges) {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }

        // BFS way
        queue<pair<int, double>> Q;
        Q.push({1, 1.0});
        int time = 0;
        vector<int> visited(n+1, false);

        while(not Q.empty()) {
            int size = Q.size();

            if (time > t) break;

            while(size--) {
                auto pp = Q.front(); Q.pop();
                int node = pp.first;
                double prob = pp.second;

                visited[node] = true;

                // Count the unvisited nbr
                int nbrCount = 0;
                for(auto& nbr : adjList[node]) {
                    if (not visited[nbr]) nbrCount++;
                }

                if (node == target) {
                    if (time == t) return prob;
                    if (time < t) {
                        // Check if any unvisited ? if yes, then frog would jump there and not be able to jump back here
                        if (nbrCount > 0) return 0.0;

                        // else return the same prob
                        return prob;
                    }
                }

                for(auto& nbr : adjList[node]) {
                    if (not visited[nbr]) {
                        // update the prob as it will be divided by number of nbr
                        Q.push({nbr, (prob * (1.0/nbrCount))});
                    }
                }
            }

            time++;
        }

        return 0.0;
    }
};
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} t
 * @param {number} target
 * @return {number}
 */
function dfs(n, map, t, target, visited, prop) {
    // edge case1: if run out of steps, cannot find target
    if(t === 0 && n !== target) return 0;
    // edge case2: if run out of steps, but found target
    if(t === 0 && n === target) return prop;

    visited.add(n);
    // get unvisited children/neighbors
    const validChildren = [];
    (map[n] ?? []).forEach((child) => {
        if(!visited.has(child)) validChildren.push(child);
    })
    // edge case3, if still more steps to use, but no more children to move,
    // if already at the targeted node, should just return
    if(n === target && t > 0 && !validChildren.length) return prop;
    // edge case4, if still more steps to use and no more children to move,
    // but current node is not target node, cannot find target, return 0
    if(n !== target && t > 0 && !validChildren.length) return 0;

    // go to next valid child/neighbor
    for(let i = 0; i < validChildren.length; i ++) {
        if(visited.has(validChildren[i])) continue;
        let result = dfs(validChildren[i], map, t - 1, target, visited, prop * (1 / validChildren.length))
        if(result !== 0) return result;
    }

    return 0;
}

var frogPosition = function(n, edges, t, target) {
    const map = new Array(n + 1);
    // make bidirectional edge map
    edges.forEach(item => {
        if(!map[item[0]]) map[item[0]] = [];
        if(!map[item[1]]) map[item[1]] = [];
        map[item[0]].push(item[1]);
        map[item[1]].push(item[0]);
    });

    return dfs(1, map, t, target, new Set(), 1);
};
Frog Position After T Seconds