Sum of Nodes and respective Neighbors on the path from root to a vertex V | Creating Adjacency list ; Function to perform DFS traversal ; Initializing parent of each node to p ; Iterate over the children ; Function to add values of children to respective parent nodes ; Root node ; Function to return sum of values of each node in path from V to the root ; Path from node V to root node ; Driver Code ; Insert edges into the graph ; Values assigned to each vertex ; Constructing the tree using adjacency list ; Parent array ; Store values in the parent array ; Add values of children to the parent ; Find sum of nodes lying in the path ; Add root node since its value is not included yet
function constructTree ( n , edges ) { let adjl = [ ] ; for ( let i = 0 ; i < n ; i ++ ) { adjl . push ( [ ] ) ; } for ( let e = 0 ; e < edges . length ; e ++ ) { let u = edges [ e ] [ 0 ] ; let v = edges [ e ] [ 1 ] ; adjl [ u ] . push ( v ) ; adjl [ v ] . push ( u ) ; } return adjl ; } function DFS ( adjl , parent , u , p ) { parent [ u ] = p ; for ( let v = 0 ; v < adjl [ u ] . length ; v ++ ) { if ( adjl [ u ] [ v ] != p ) { DFS ( adjl , parent , adjl [ u ] [ v ] , u ) ; } } } function valuesFromChildren ( parent , values ) { let valuesChildren = new Array ( parent . length ) ; for ( let i = 0 ; i < parent . length ; i ++ ) { valuesChildren [ i ] = 0 ; } for ( let i = 0 ; i < parent . length ; i ++ ) { if ( parent [ i ] == - 1 ) continue ; else { let p = parent [ i ] ; valuesChildren [ p ] += values [ i ] ; } } return valuesChildren ; } function findSumOfValues ( v , parent , valuesChildren ) { let cur_node = v ; let sum = 0 ; while ( cur_node != - 1 ) { sum += valuesChildren [ cur_node ] ; cur_node = parent [ cur_node ] ; } return sum ; } let n = 8 ; let edges = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 0 , 3 ] , [ 1 , 4 ] , [ 1 , 5 ] , [ 4 , 7 ] , [ 3 , 6 ] ] ; let v = 7 ; let values = [ 1 , 2 , 3 , 0 , 0 , 4 , 3 , 6 ] ; let adjl = constructTree ( n , edges ) ; let parent = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { parent [ i ] = 0 ; } DFS ( adjl , parent , 0 , - 1 ) ; let valuesChildren = valuesFromChildren ( parent , values ) ; let sum = findSumOfValues ( v , parent , valuesChildren ) ; sum += values [ 0 ] ; document . write ( sum ) ;