Frog Position After T Seconds

Explore how to calculate the probability that a frog, starting at the root of an undirected tree, will be on a specified target vertex after t seconds. Understand how to apply breadth-first search to analyze the frog's movement rules, including random jumps to unvisited neighbors and staying put when stuck, enabling you to solve similar node traversal problems effectively.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

You are given an undirected tree with n vertices labeled from $1$ to $n$ . A frog starts at vertex $1$ , at time $0$ , and makes one move per second.

At each step, the frog follows these rules:

Move to an unvisited neighbor:
If the frog has unvisited neighbors, it jumps to one of them, chosen uniformly at random (equal probability for each choice).
No revisiting:
The frog can not jump back to a vertex it has already visited.
Stay when stuck
The frog will keep jumping at its current vertex if there are no unvisited neighbors.

The tree is represented as an array of edges, where edges[i] = [ $a_i$ ...