# GGBHAI - Editorial

Author: Rishabh Gupta

Tester: Suraj Kumar

Editorialist: Rishabh Gupta

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:

can some one look into the code its perfectly following the logic
im getting wrong answer dunno why??

import java.lang.;
import java.util.
;

//implementing undirected graph in java

public class Graph {

``````//function to add an edge between vertices U and V
}

//function to print graph with respective vertices and edges
System.out.print("==>");
System.out.print(" "+y+" ");
}
System.out.println();
}
}

//function implementing breadth first Search (bfs)
public static double bfs(int start,int numberOfVertices,ArrayList<ArrayList<Integer>> adjlist,int[] rest){
boolean[] visited = new boolean[numberOfVertices+1];        //boolean array to check if vertex
for(boolean val:visited){                                   //is visited or not
val = false;
}
int [] level = new int[numberOfVertices+1];
visited[start] = true;
level[start] = 0;

while(queue.isEmpty() != true){                         //putting starting element on top and checking
int top  = queue.poll();                            //its neighbours ,if they are not visited
//System.out.println(top);                            //visiting them and pushing them in the queue
if(visited[neighbour] == false){
level[neighbour]=level[top]+1;
visited[neighbour] = true;
}
}
}
float total = 0;
for(int y:rest)
total+=level[y];

return 2.0*total;
}

public static void main(String[] args) throws java.lang.Exception{

Scanner input = new Scanner(System.in);
int testcases = input.nextInt();
for (int i = 0;i<testcases;i++){
int n = input.nextInt();
int  m  = input.nextInt();
int numberOfVertices = n+1;

for (int num=0;num<numberOfVertices+1;num++){
}

for (int j=0;j<n-1;j++){
int u = input.nextInt();
int v = input.nextInt();
}
int [] rest = new int[m];
for (int res = 0;res<m;res++){
rest[res] = input.nextInt();
}