Sum of lengths of all paths possible in a given tree | Javascript 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
let sz = 100005 ; let n ; let tree = new Array ( sz ) ; let subtree_size = new Array ( sz ) ; let vis = new Array ( sz ) ; function AddEdge ( a , b ) { tree [ a ] . push ( b ) ; tree [ b ] . push ( a ) ; } function dfs ( node ) { vis [ node ] = 1 ; subtree_size [ node ] = 1 ; for ( let child = 0 ; child < tree [ node ] . length ; child ++ ) { if ( vis [ tree [ node ] [ child ] ] == 0 ) { subtree_size [ node ] += dfs ( tree [ node ] [ child ] ) ; } } return subtree_size [ node ] ; } function contribution ( node , ans ) { vis [ node ] = 1 ; for ( let child = 0 ; child < tree [ node ] . length ; child ++ ) { if ( vis [ tree [ node ] [ child ] ] == 0 ) { ans += ( subtree_size [ tree [ node ] [ child ] ] * ( n - subtree_size [ tree [ node ] [ child ] ] ) ) ; ans = contribution ( tree [ node ] [ child ] , ans ) ; } } return ans ; } function getSum ( ) { for ( let i = 0 ; i < vis . length ; i ++ ) { vis [ i ] = 0 ; } dfs ( 0 ) ; let ans = 0 ; for ( let i = 0 ; i < vis . length ; i ++ ) { vis [ i ] = 0 ; } ans = contribution ( 0 , ans ) ; return ans ; } n = 5 ; for ( let i = 0 ; i < sz ; i ++ ) { tree [ i ] = [ ] ; } AddEdge ( 0 , 1 ) ; AddEdge ( 0 , 2 ) ; AddEdge ( 1 , 3 ) ; AddEdge ( 1 , 4 ) ; document . write ( getSum ( ) ) ;