human
Can you provide a code to sum of Nodes and respective Neighbors on the path from root to a vertex V and the other steps required given the following:
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"
How can the above be solved in Python?
assistant
#Here is code to sum of Nodes and respective Neighbors on the path from root to a vertex V and the other steps required.
 def constructTree ( n , edges ) :
	adjl = [ ]
	for i in range ( n ) :
		adjl . append ( [ ] )
	for i in range ( len ( edges ) ) :
		u = edges [ i ] [ 0 ]
		v = edges [ i ] [ 1 ]
		adjl [ u ] . append ( v )
		adjl [ v ] . append ( u )
	return adjl
def DFS ( adjl , parent , u , p ) :
	parent [ u ] = p
	for v in adjl [ u ] :
		if ( v != p ) :
			DFS ( adjl , parent , v , u )
def valuesFromChildren ( parent , values ) :
	valuesChildren = [ 0 ] * ( len ( parent ) )
	for i in range ( len ( parent ) ) :
		if ( parent [ i ] == - 1 ) :
			continue
		else :
			p = parent [ i ]
			valuesChildren [ p ] += values [ i ]
	return valuesChildren
def findSumOfValues ( v , parent , valuesChildren ) :
	cur_node = v
	Sum = 0
	while ( cur_node != - 1 ) :
		Sum += valuesChildren [ cur_node ]
		cur_node = parent [ cur_node ]
	return Sum
n = 8
edges = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 0 , 3 ] , [ 1 , 4 ] , [ 1 , 5 ] , [ 4 , 7 ] , [ 3 , 6 ] ]
v = 7
values = [ 1 , 2 , 3 , 0 , 0 , 4 , 3 , 6 ]
adjl = constructTree ( n , edges )
parent = [ 0 ] * ( n )
DFS ( adjl , parent , 0 , - 1 )
valuesChildren = valuesFromChildren ( parent , values )
Sum = findSumOfValues ( v , parent , valuesChildren )
Sum += values [ 0 ]
print ( Sum )