Count pairs of nodes having minimum distance between them equal to the difference of their distances from root | Java program for the above approach ; Stores the count of pairs ; Store the adjacency list of the connecting vertex ; Function for theto perform DFS traversal of the given tree ; Traverse the adjacency list of the current node u ; If the current node is the parent node ; Add number of ancestors , which is same as depth of the node ; Function for DFS traversal of the given tree ; Print the result ; Function to find the count of pairs such that the minimum distance between them is equal to the difference between distance of the nodes from root node ; Add edges to adj [ ] ; Driver Code
import java . util . * ; class GFG { static int ans = 0 ; static ArrayList < Integer > [ ] adj = new ArrayList [ ( int ) ( 1e5 ) + 1 ] ; static { for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new ArrayList < > ( ) ; } static void dfsUtil ( int u , int par , int depth ) { for ( int it : adj [ u ] ) { if ( it != par ) { dfsUtil ( it , u , depth + 1 ) ; } } ans += depth ; } static void dfs ( int u , int par , int depth ) { dfsUtil ( u , par , depth ) ; System . out . print ( ans + "NEW_LINE"); } static void countPairs ( int [ ] [ ] edges ) { for ( int i = 0 ; i < edges . length ; i ++ ) { int u = edges [ i ] [ 0 ] ; int v = edges [ i ] [ 1 ] ; adj [ u ] . add ( v ) ; adj [ v ] . add ( u ) ; } dfs ( 1 , 1 , 1 ) ; } public static void main ( String [ ] args ) { int [ ] [ ] edges = { { 1 , 2 } , { 1 , 3 } , { 2 , 4 } } ; countPairs ( edges ) ; } }