### 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.