用BFS往下搜索，同时用prob数组记录答案

class Solution {
public:
    vector<vector<int>> adj;
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        adj.resize(n+1);
        for (auto &e : edges){
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<double> prob(n+1, -1);
        queue<int> q;

        prob[1] = 1;
        q.push(1);
        while (t--){
            for (int i = 0, siz = q.size(); i < siz; i++){
                auto u = q.front(); q.pop();

                bool isLeft = false;
                for (auto v : adj[u]){
                    if (prob[v] == 0)   continue;
                    isLeft =true;
                    q.push(v);
                    prob[v] = prob[u] / (adj[u].size() - (u != 1));
                }
                if (isLeft) prob[u] = 0;
            }
        }
        return prob[target] == -1 ? 0 : prob[target];
    }
};