<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 {
public:

    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<int> child(n, 0);  // Keep track of number of children for each node
        unordered_map<int, vector<int>> adj;
        if(edges.empty() && target==1) return 1.0;
        if(target==1 && t!=0) return 0.0;
        // Build adjacency list
        for(int i = 0; i < edges.size(); i++){
            adj[edges[i][0] - 1].push_back(edges[i][1] - 1);
            adj[edges[i][1] - 1].push_back(edges[i][0] - 1);
        }
        
        vector<int> parent(n, -1);  // Keep track of parents
        vector<bool> vis(n, false);  // Visited array
        queue<pair<int,int>> q;
        
        q.push({0, 0});
        vis[0] = true;
        int dis = -1;
        
        // BFS to find target and distance from root
        while(!q.empty()){
            int node = q.front().first;
            int d = q.front().second;
            q.pop();
            
            if(node == target - 1) {  // Zero-based target
                dis = d;
                break;
            }
            
            for(auto v : adj[node]){
                if(!vis[v]){
                    vis[v] = true;
                    parent[v] = node;
                    q.push({v, d + 1});
                }
            }
        }
        for(int i=0;i<=target-1;i++) cout<<parent[i]<<" ";
        cout<<endl;
        if(dis > t){  // If distance to target exceeds time
            return 0.0;
        } else if(dis < t){
            // Check if it is a leaf node, meaning it cannot stop earlier
            if(adj[target - 1].size() != 1 && target != 1) {  // Target is not the root and not a leaf
                return 0.0;
            } else {
                double prob = 1.0;
                int node = target - 1;
                for(int i=0;i<n;i++){
                    cout<<adj[i].size()<<" ";
                }
                cout<<endl;
                // Calculate probability from target to root
                while(node != 0){
                    if(parent[parent[node]]==-1){
                        prob*=1.0/(adj[parent[node]].size());
                    }else{
                    prob *= 1.0 / (adj[parent[node]].size()-1 );
                    }
                   // -1 to exclude the parent itself
                    node = parent[node];
                }
             
                return prob;
            }
        }else{
              double prob = 1.0;
                int node = target - 1;
                for(int i=0;i<n;i++){
                    cout<<adj[i].size()<<" ";
                }
                cout<<endl;
                // Calculate probability from target to root
                while(node != 0){
                    if(parent[parent[node]]==-1){
                        prob*=1.0/(adj[parent[node]].size());
                    }else{
                    prob *= 1.0 / (adj[parent[node]].size()-1 );
                    }
                   // -1 to exclude the parent itself
                    node = parent[node];
                }
             
                return prob;
        }
        
        return 0.0;
    }
};

21200