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:
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
//using Adjacency Lists
public class Graph {
//function to add an edge between vertices U and V
public static void addEdge(ArrayList<ArrayList<Integer>> adjList,int U,int V){
adjList.get(U).add(V);
adjList.get(V).add(U);
}
//function to print graph with respective vertices and edges
public static void printGraph(ArrayList<ArrayList<Integer>>adjList){
for(int x = 0; x<adjList.size();x++){
System.out.println("Adjacency list of vertex "+x);
System.out.print("==>");
for(int y :adjList.get(x)){
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;
var queue = new LinkedList<Integer>();
queue.add(start);
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
for(int neighbour:adjlist.get(top)){
if(visited[neighbour] == false){
level[neighbour]=level[top]+1;
visited[neighbour] = true;
queue.add(neighbour);
}
}
}
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;
ArrayList<ArrayList<Integer>> adjList;
adjList = new ArrayList<ArrayList<Integer>>(numberOfVertices+1);
for (int num=0;num<numberOfVertices+1;num++){
adjList.add(new ArrayList<>());
}
for (int j=0;j<n-1;j++){
int u = input.nextInt();
int v = input.nextInt();
addEdge(adjList,u,v);
}
int [] rest = new int[m];
for (int res = 0;res<m;res++){
rest[res] = input.nextInt();
}
float res = (float) ((1.0*bfs(1,numberOfVertices,adjList,rest))/m);
System.out.printf("%f",res);
System.out.println();
}
}
}