Queries to find the count of shortest paths in a Tree that contains a given edge | Java implementation for the above approach ; Adjacency list to represent the tree ; Number of vertices ; Mark visited / unvisited vertices ; Stores the subtree size of the corresponding nodes ; Function to create an edge between two vertices ; Add a to b 's list ; Add b to a 's list ; Function to perform DFS ; Mark the vertex visited ; Include the node in the subtree ; Traverse all its children ; Function to print the required number of paths ; Driver Code ; Number of vertices ; Calling modified dfs function ; Count pairs of vertices in the tree
import java . util . * ; class GFG { static int sz = ( int ) 1e5 ; static Vector < Integer > [ ] tree = new Vector [ sz ] ; static int n ; static boolean [ ] vis = new boolean [ sz ] ; static int [ ] subtreeSize = new int [ sz ] ; static void addEdge ( int a , int b ) { tree [ a ] . add ( b ) ; tree [ b ] . add ( a ) ; } static void dfs ( int x ) { vis [ x ] = true ; subtreeSize [ x ] = 1 ; for ( int i : tree [ x ] ) { if ( ! vis [ i ] ) { dfs ( i ) ; subtreeSize [ x ] += subtreeSize [ i ] ; } } } static void countPairs ( int a , int b ) { int sub = Math . min ( subtreeSize [ a ] , subtreeSize [ b ] ) ; System . out . print ( sub * ( n - sub ) + "NEW_LINE"); } public static void main ( String [ ] args ) { n = 6 ; for ( int i = 0 ; i < tree . length ; i ++ ) tree [ i ] = new Vector < Integer > ( ) ; addEdge ( 0 , 1 ) ; addEdge ( 0 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 3 , 4 ) ; addEdge ( 3 , 5 ) ; dfs ( 0 ) ; countPairs ( 1 , 3 ) ; countPairs ( 0 , 2 ) ; } }