GGBHAI - Editorial

PROBLEM LINK:

Practice
Contest

Author: Rishabh Gupta

Tester: Suraj Kumar

Editorialist: Rishabh Gupta

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Levels in Tree, BFS, Expected value

PROBLEM:

Given a tree with N nodes, and M special nodes. You have to find the distance from root node (1) to those special M nodes
and calculate the expected distance with probability of selection of each of those M nodes to be equal.

EXPLANATION:

One can find the distance of those M nodes one by one, and then calculate the expected distance. This will take longer time.
Instead, since each road is 1 unit long, we can simply calculate the levels of those M nodes.
So, a node at level k, will have a distance of k units, (with root node assigned a level 0).
This way the distance travelled by the character will be 2*k units (going from root to node and then returning back).
Now we can sum these up and divide by M, as the probability of choosing any one node is 1/M.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

//