PROBLEM LINK:
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.