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
def constructTree ( n , edges ) : NEW_LINE INDENT adjl = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT adjl . append ( [ ] ) NEW_LINE DEDENT for i in range ( len ( edges ) ) : NEW_LINE INDENT u = edges [ i ] [ 0 ] NEW_LINE v = edges [ i ] [ 1 ] NEW_LINE adjl [ u ] . append ( v ) NEW_LINE adjl [ v ] . append ( u ) NEW_LINE DEDENT return adjl NEW_LINE DEDENT def DFS ( adjl , parent , u , p ) : NEW_LINE INDENT parent [ u ] = p NEW_LINE for v in adjl [ u ] : NEW_LINE INDENT if ( v != p ) : NEW_LINE INDENT DFS ( adjl , parent , v , u ) NEW_LINE DEDENT DEDENT DEDENT def valuesFromChildren ( parent , values ) : NEW_LINE INDENT valuesChildren = [ 0 ] * ( len ( parent ) ) NEW_LINE for i in range ( len ( parent ) ) : NEW_LINE INDENT if ( parent [ i ] == - 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT p = parent [ i ] NEW_LINE valuesChildren [ p ] += values [ i ] NEW_LINE DEDENT DEDENT return valuesChildren NEW_LINE DEDENT def findSumOfValues ( v , parent , valuesChildren ) : NEW_LINE INDENT cur_node = v NEW_LINE Sum = 0 NEW_LINE while ( cur_node != - 1 ) : NEW_LINE INDENT Sum += valuesChildren [ cur_node ] NEW_LINE cur_node = parent [ cur_node ] NEW_LINE DEDENT return Sum NEW_LINE DEDENT n = 8 NEW_LINE edges = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 0 , 3 ] , [ 1 , 4 ] , [ 1 , 5 ] , [ 4 , 7 ] , [ 3 , 6 ] ] NEW_LINE v = 7 NEW_LINE values = [ 1 , 2 , 3 , 0 , 0 , 4 , 3 , 6 ] NEW_LINE adjl = constructTree ( n , edges ) NEW_LINE parent = [ 0 ] * ( n ) NEW_LINE DFS ( adjl , parent , 0 , - 1 ) NEW_LINE valuesChildren = valuesFromChildren ( parent , values ) NEW_LINE Sum = findSumOfValues ( v , parent , valuesChildren ) NEW_LINE Sum += values [ 0 ] NEW_LINE print ( Sum ) NEW_LINE