<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> adj[n+1];
//         for(int i=0;i<n;i++){
//             adj[edges[i][0]].push_back(edges[i][1]);
//             adj[edges[i][1]].push_back(edges[i][0]);
//         }

//         adj[1].push_back(0);

//         queue<pair<int,double>> q;
//         vector<int> visited(n+1,0);
//         q.push({1,1.00});
//         visited[1]=1;
//         visited[0]=1;
//         int level=0;
//         while(q.size()!=0){
//             int size=q.size();
//             while(size--){
//                 int currInd=q.front().first;
//                 double currProb=q.front().second;
//                 q.pop();

//                 if(currInd==target){
//                     if(adj[currInd].size()==1 && level<=t){
//                         return currProb;
//                     }
//                     else if(level==t){
//                         return currProb;
//                     }
//                     else{
//                         return 0.00;
//                     }

//                 }

//                 int s=adj[currInd].size()-1;
//                 if(s<=0) continue;
//                 for(auto child:adj[currInd]){
//                     double prob=(double)currProb/ s;
//                     if(visited[child]==0 && child>0){
//                         q.push({child,prob});
//                         visited[child]=1;
//                     }
//                 }
//             }
//             level++;
//         }
//         return 0.00;
//     }
// };
class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<int> adj[n+1];
        // Build the adjacency list
        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]);
        }

        // To avoid boundary case issues, include a dummy node 0
        adj[1].push_back(0); 

        // Queue to perform BFS, with {node, probability}
        queue<pair<int, double>> q;
        vector<int> visited(n+1, 0);
        q.push({1, 1.00});  // Starting from node 1 with 100% probability
        visited[1] = 1;      // Mark node 1 as visited
        visited[0] = 1;      // Dummy node to avoid edge cases

        int level = 0;       // Track the time

        // BFS Loop
        while (!q.empty()) {
            int size = q.size(); // Nodes at the current level
            while (size--) {
                int currInd = q.front().first;      // Current node
                double currProb = q.front().second; // Probability of being at the current node
                q.pop();

                // If we reach the target node
                if (currInd == target) {
                    // If it's a leaf node or we've reached the target at time t
                    if (adj[currInd].size() == 1 && level <= t) {
                        return currProb;
                    }
                    // If we reach exactly at time t, return the probability
                    else if (level == t) {
                        return currProb;
                    }
                    // Otherwise, if we reached earlier, return 0
                    else {
                        return 0.00;
                    }
                }

                // Count the number of unvisited children (excluding the parent)
                int unvisitedChildren = 0;
                for (auto child : adj[currInd]) {
                    if (visited[child] == 0 ) {
                        unvisitedChildren++;
                    }
                }

                // Traverse unvisited children
                for (auto child : adj[currInd]) {
                    if (visited[child] == 0 && child > 0) {
                        q.push({child, currProb / unvisitedChildren}); // Divide probability equally
                        visited[child] = 1;  // Mark as visited
                    }
                }
            }
            level++;  // Move to the next level (next second)
            if (level > t) break;  // Stop once we pass time t
        }

        return 0.00;  // If we didn't reach the target at the correct time
    }
};

19000