Sum of lengths of all paths possible in a given tree | Java implementation of the approach ; Number of vertices ; Adjacency list representation of the tree ; Array that stores the subtree size ; Array to mark all the vertices which are visited ; Utility function to create an edge between two vertices ; Add a to b 's list ; Add b to a 's list ; Function to calculate the subtree size ; Mark visited ; For every adjacent node ; If not already visited ; Recursive call for the child ; Function to calculate the contribution of each edge ; Mark current node as visited ; For every adjacent node ; If it is not already visisted ; Function to return the required sum ; First pass of the dfs ; Second pass ; Driver code
import java . util . * ; @ SuppressWarnings ( " unchecked " ) class GFG { static int sz = 100005 ; static int n ; static ArrayList [ ] tree = new ArrayList [ sz ] ; static int [ ] subtree_size = new int [ sz ] ; static int [ ] vis = new int [ sz ] ; static void AddEdge ( int a , int b ) { tree [ a ] . add ( b ) ; tree [ b ] . add ( a ) ; } static int dfs ( int node ) { vis [ node ] = 1 ; subtree_size [ node ] = 1 ; for ( int child : ( ArrayList < Integer > ) tree [ node ] ) { if ( vis [ child ] == 0 ) { subtree_size [ node ] += dfs ( child ) ; } } return subtree_size [ node ] ; } static int contribution ( int node , int ans ) { vis [ node ] = 1 ; for ( int child : ( ArrayList < Integer > ) tree [ node ] ) { if ( vis [ child ] == 0 ) { ans += ( subtree_size [ child ] * ( n - subtree_size [ child ] ) ) ; ans = contribution ( child , ans ) ; } } return ans ; } static int getSum ( ) { Arrays . fill ( vis , 0 ) ; dfs ( 0 ) ; int ans = 0 ; Arrays . fill ( vis , 0 ) ; ans = contribution ( 0 , ans ) ; return ans ; } public static void main ( String [ ] args ) { n = 5 ; for ( int i = 0 ; i < sz ; i ++ ) { tree [ i ] = new ArrayList ( ) ; } AddEdge ( 0 , 1 ) ; AddEdge ( 0 , 2 ) ; AddEdge ( 1 , 3 ) ; AddEdge ( 1 , 4 ) ; System . out . println ( getSum ( ) ) ; } }