Largest subtree sum for each vertex of given N | C ++ program for the above approach ; Function to perform the DFS Traversal on the given Tree ; To check if v is leaf vertex ; Initialize answer for vertex v ; Traverse adjacency list of v ; Update maximum subtree sum ; If v is leaf ; Function to calculate maximum subtree sum for each vertex ; Stores the adjacency list ; Add Edegs to the list ; Stores largest subtree sum for each vertex ; Calculate answer ; Print the result ; Driver Code ; Given nodes ; Give N edges ; Given values ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define V  3 NEW_LINE #define M  2 NEW_LINE void dfs ( int v , int p , vector < int > adj [ ] , int ans [ ] , int vals [ ] ) { bool isLeaf = 1 ; ans [ v ] = INT_MIN ; for ( int u : adj [ v ] ) { if ( u == p ) continue ; isLeaf = 0 ; dfs ( u , v , adj , ans , vals ) ; ans [ v ] = max ( ans [ u ] + vals [ v ] , max ( ans [ u ] , vals [ u ] ) ) ; } if ( isLeaf ) { ans [ v ] = vals [ v ] ; } } void printAnswer ( int n , int edges [ V ] [ M ] , int values [ ] ) { vector < int > adj [ n ] ; for ( int i = 0 ; i < n - 1 ; i ++ ) { int u = edges [ i ] [ 0 ] - 1 ; int v = edges [ i ] [ 1 ] - 1 ; adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } int ans [ n ] ; dfs ( 0 , -1 , adj , ans , values ) ; for ( auto x : ans ) { cout << x << " ▁ " ; } } int main ( ) { int N = 4 ; int edges [ V ] [ M ] = { { 1 , 2 } , { 1 , 3 } , { 3 , 4 } } ; int values [ ] = { 1 , -1 , 0 , 1 } ; printAnswer ( N , edges , values ) ; }