1377. Frog Position After T Seconds

题目信息

题号:

1377

难度:

Hard

主题:

树、概率、深度优先搜索

原题:

LeetCode 1377

重点:

青蛙从节点 1 开始,每秒等概率跳到尚未访问的相邻节点;没有未访问邻居时留在原地

题目重述

给定一棵包含 n 个节点的无向树。青蛙初始位于节点 1。每秒钟,若当前位置存在未访问过的相邻节点,它会从这些节点中等概率选择一个跳过去;若不存在,则继续停留在当前位置。

请返回恰好 t 秒后青蛙位于 target 节点的概率。已经访问过的节点不能再次跳入。

1 <= n <= 100,0 <= t <= 50,树边数为 n-1。

自建示例

根的两个孩子被等概率选择:

输入:n = 3, edges = [[1,2],[1,3]], t = 1, target = 2
输出:0.5
解释:第一秒从两个未访问邻居中等概率选择。

到达叶节点后会继续停留:

输入:同一棵树,t = 2, target = 2
输出:0.5
解释:第一秒到达节点 2 的概率为二分之一,之后没有未访问邻居,因此留在节点 2。