Sum of Nodes and respective Neighbors on the path from root to a vertex V | Java Program to implement the above approach ; 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
import java . io . * ; import java . util . * ; class GFG { private static List < List < Integer > > constructTree ( int n , int [ ] [ ] edges ) { List < List < Integer > > adjl = new ArrayList < List < Integer > > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { adjl . add ( new ArrayList < Integer > ( ) ) ; } for ( int [ ] e : edges ) { int u = e [ 0 ] ; int v = e [ 1 ] ; adjl . get ( u ) . add ( v ) ; adjl . get ( v ) . add ( u ) ; } return adjl ; } private static void DFS ( List < List < Integer > > adjl , int [ ] parent , int u , int p ) { parent [ u ] = p ; for ( int v : adjl . get ( u ) ) { if ( v != p ) { DFS ( adjl , parent , v , u ) ; } } } private static int [ ] valuesFromChildren ( int [ ] parent , int [ ] values ) { int [ ] valuesChildren = new int [ parent . length ] ; for ( int i = 0 ; i < parent . length ; i ++ ) { if ( parent [ i ] == - 1 ) continue ; else { int p = parent [ i ] ; valuesChildren [ p ] += values [ i ] ; } } return valuesChildren ; } private static int findSumOfValues ( int v , int [ ] parent , int [ ] valuesChildren ) { int cur_node = v ; int sum = 0 ; while ( cur_node != - 1 ) { sum += valuesChildren [ cur_node ] ; cur_node = parent [ cur_node ] ; } return sum ; } public static void main ( String [ ] args ) { int n = 8 ; int [ ] [ ] edges = { { 0 , 1 } , { 0 , 2 } , { 0 , 3 } , { 1 , 4 } , { 1 , 5 } , { 4 , 7 } , { 3 , 6 } } ; int v = 7 ; int [ ] values = new int [ ] { 1 , 2 , 3 , 0 , 0 , 4 , 3 , 6 } ; List < List < Integer > > adjl = constructTree ( n , edges ) ; int [ ] parent = new int [ n ] ; DFS ( adjl , parent , 0 , - 1 ) ; int [ ] valuesChildren = valuesFromChildren ( parent , values ) ; int sum = findSumOfValues ( v , parent , valuesChildren ) ; sum += values [ 0 ] ; System . out . println ( sum ) ; } }