Sum of Nodes and respective Neighbors on the path from root to a vertex V | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < int > > constructTree ( int n , vector < vector < int > > edges ) { vector < vector < int > > adjl ( n ) ; for ( auto e : edges ) { int u = e [ 0 ] ; int v = e [ 1 ] ; adjl [ u ] . push_back ( v ) ; adjl [ v ] . push_back ( u ) ; } return adjl ; } void DFS ( vector < vector < int > > adjl , vector < int > & parent , int u , int p ) { parent [ u ] = p ; for ( int v : adjl [ u ] ) { if ( v != p ) { DFS ( adjl , parent , v , u ) ; } } } vector < int > valuesFromChildren ( vector < int > parent , vector < int > values ) { vector < int > valuesChildren ( parent . size ( ) ) ; for ( int i = 0 ; i < parent . size ( ) ; i ++ ) { if ( parent [ i ] == -1 ) continue ; else { int p = parent [ i ] ; valuesChildren [ p ] += values [ i ] ; } } return valuesChildren ; } int findSumOfValues ( int v , vector < int > parent , vector < int > valuesChildren ) { int cur_node = v ; int sum = 0 ; while ( cur_node != -1 ) { sum += valuesChildren [ cur_node ] ; cur_node = parent [ cur_node ] ; } return sum ; } int main ( ) { int n = 8 ; vector < vector < int > > edges = { { 0 , 1 } , { 0 , 2 } , { 0 , 3 } , { 1 , 4 } , { 1 , 5 } , { 4 , 7 } , { 3 , 6 } } ; int v = 7 ; vector < int > values = { 1 , 2 , 3 , 0 , 0 , 4 , 3 , 6 } ; vector < vector < int > > adjl = constructTree ( n , edges ) ; vector < int > parent ( n ) ; DFS ( adjl , parent , 0 , -1 ) ; vector < int > valuesChildren = valuesFromChildren ( parent , values ) ; int sum = findSumOfValues ( v , parent , valuesChildren ) ; sum += values [ 0 ] ; cout << sum << endl ; }