The opportunity could be easily calculated by DFS.
In additional to the general DFS, we need to first pay attention to the time we left. If it is less than 0, we should stop the DFS process.
Then, we need to pass the current opportunity as an additional variable to the DFS function. So we could use it as the return value when we find the target.
class Solution: def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float: # Build up the tree target -= 1 adj = [ for _ in range(n)] for i, j in edges: adj[i - 1].append(j - 1) adj[j - 1].append(i - 1) # Do a DFS to get the opportunities return self._dfs(0, -1, adj, t, target, 1.) def _dfs(self, node, parent, adj, timeLeft, target, opportunity): if parent == -1: tmp = len(adj[node]) else: tmp = len(adj[node]) - 1 if node is target: if timeLeft == 0 or tmp == 0: return opportunity return 0 elif timeLeft == 0: return 0. if tmp == 0: return 0. opportunity = opportunity / tmp for child in adj[node]: if child != parent: tmp = self._dfs(child, node, adj, timeLeft - 1, target, opportunity) if tmp > 0: return tmp return 0.