5355. T 秒后青蛙的位置


图片说明
图片说明


dfs,分类讨论

class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<int>g[n+2];
        double dp[105];
        dp[1]=1.0;
        for(auto v:edges){
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }
        function<void(int u,int fa,int dep)>dfs=[&](int u,int fa,int dep){
            int sz=0;
            for(int v:g[u])if(v!=fa)sz++;
            if(u==target){
                if(sz>0){
                    if(dep-1==t)return;
                    else dp[u]=0;
                }
                if(dep-1>t)dp[u]=0;
                return;
            }
            for(int v:g[u]){
                if(v!=fa){
                    dp[v]=dp[u]*1.0/sz;
                    dfs(v,u,dep+1);
                }
            }
        };
        dfs(1,0,1);
        return dp[target];
    }
};