Mode: On-Campus Exam Pattern: 3 dsa questions OA Date: 2026-10-09

Frog Position After T Seconds

You are given an undirected tree consisting of N nodes numbered from 1 to N. A frog starts at node 1.

Every second, the frog jumps from its current node to an unvisited adjacent node. The frog cannot visit a previously visited node again.

https://leetcode.com/problems/frog-position-after-t-seconds/description/

If there are multiple unvisited adjacent nodes, the frog chooses one randomly, with equal probability for each available node.

If the frog has no unvisited adjacent nodes, it stays at its current node forever.

You are given an integer T representing the number of seconds and an integer target representing the target node.

Your task is to calculate the probability that the frog is at the target node after exactly T seconds.

Input Format

The first line contains an integer N, representing the number of nodes.
The next N - 1 lines contain two integers u and v, representing an undirected edge between nodes u and v.
The next line contains two integers T and target, representing the time in seconds and the target node.

Output Format

Print the probability that the frog is at the target node after exactly T seconds.

Answers with an absolute error of at most 10^-5 are accepted.

Constraints

1 ≤ N ≤ 100
Number of edges = N - 1
1 ≤ T ≤ 50
1 ≤ target ≤ N

Sample Input 1

Sample Output 1

0.1666666667

Explanation

Initially, the frog is at node 1.

After 1 second, the frog can move to node 2, node 3, or node 7, each with probability 1/3.
To reach node 4, the frog must first move to node 2, with probability 1/3.
From node 2, it can move to node 4 or node 6, each with probability 1/2.

Therefore, the probability of reaching node 4 after exactly 2 seconds is:

Probability = (1/3) × (1/2) = 1/6 = 0.1666666667.

Sample Input 2

Sample Output 2

0.3333333333