!Probability
Practice
2.9 (12 votes)
Algorithms
Depth First search
Trees
Dynamic programming
Problem
33% Success 1105 Attempts 30 Points 1s Time Limit 512MB Memory 1024 KB Max Code

Given a tree with \(N\) nodes and \(N - 1\) edges rooted at node \(1\). You have to answer \(Q\) queries. In every query, you will be given a node \(x\).

Alice will tell his friend Bob the distance from \(1\) to \(x\). But Bob only knows how to reach a particular distance from \(1\). Find the probability that Bob will reach \(x\) in one try. If \(P\) will be the probability then print \(\frac{1}{P}\) in each query.

Note - The distance between two vertices in a tree is equal to the number of edges on the unique simple path between them.

Input Format

  • The first line contains \(N\) and \(Q\) — number of nodes and queries.
  • The next  \(N-1\) lines follow. The \(i^{th}\) line contains two integers \(X_i, Y_i\) denoting an edge between the nodes \(X_i,Y_i\). It is guaranteed that the given nodes and edges form a tree.
  • The next \(Q\) lines contain a node \(x\).

Output Format

For each query, If \(P\) will be the probability to  reach \(x\) in one try then print \(\frac{1}{P}\) in a separate line.

Constraints

\(1 \leq N, Q \leq 10^5 \\ 1 \leq X_i, Y_i \leq N \\ X_i \neq Y_i \\ 1 \leq x \leq N\)

 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
3 votes
Tags:
TreeDynamic ProgrammingAlgorithmsMedium
Points:30
3 votes
Tags:
dynamic programmingTreebitmaskMediumAlgorithmsDynamic Programming
Points:30
1 votes
Tags:
Dynamic ProgrammingTreeMediumAlgorithmsKadaneDepth-first search