<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:
    pair<int,double> bfs(int node, vector<int> adj[], vector<int>& vis, int target, int t) {
        queue<pair<int, double>> q;  // Queue stores {node, probability}
        q.push({node, 1.0});  // Start at node 1 with probability 1.0
        vis[node] = true;
        
        int time = 0;  // Track the time taken to reach nodes
        
        while (!q.empty()) {
            int q_size = q.size();  // Process all nodes at the current time level
            for (int i = 0; i < q_size; ++i) {
                auto u = q.front();
                q.pop();
                
                int v = u.first;      // Current node
                double p = u.second;  // Current probability
                
                // If we reached the target within the allowed time
                if (v == target) {
                    // If we're at a leaf or out of time, return the current probability
                    if (adj[v].size() == (v == 1 ? 0 : 1) || time == t) {
                        return {v, p};
                    } else {
                        return {v, 0.0};  // Otherwise, frog jumps away, so probability is 0
                    }
                }
                
                int nof_childs = 0;  // Count unvisited children
                for (auto i : adj[v]) {
                    if (!vis[i]) {
                        ++nof_childs;
                    }
                }
                
                for (auto i : adj[v]) {
                    if (!vis[i]) {
                        vis[i] = true;
                        q.push({i, p / nof_childs});  // Divide the probability among children
                    }
                }
            }
            
            ++time;  // Increment the time after processing one level
            if (time > t) break;  // Stop if time exceeds t
        }
        
        return {-1, 0.0};  // If target isn't reached, return 0 probability
    }
    
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<int> adj[n+1];
        
        for (int i = 0; i < edges.size(); ++i) {
            adj[edges[i][0]].push_back(edges[i][1]);
            adj[edges[i][1]].push_back(edges[i][0]);
        }
        
        vector<int> vis(n+1, false);  // Visited array to track visited nodes
        auto res = bfs(1, adj, vis, target, t);  // Start BFS from node 1
        
        return res.second;  // Return the probability of reaching the target
    }
};

19200