Largest subtree sum for each vertex of given N | Java 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
import java . io . * ; import java . util . ArrayList ; @ SuppressWarnings ( " unchecked " ) class GFG { static void dfs ( int v , int p , ArrayList < Integer > adj [ ] , int ans [ ] , int vals [ ] ) { boolean isLeaf = true ; ans [ v ] = Integer . MIN_VALUE ; for ( int u : adj [ v ] ) { if ( u == p ) continue ; isLeaf = false ; dfs ( u , v , adj , ans , vals ) ; ans [ v ] = Math . max ( ans [ u ] + vals [ v ] , Math . max ( ans [ u ] , vals [ u ] ) ) ; } if ( isLeaf ) { ans [ v ] = vals [ v ] ; } } static void printAnswer ( int n , int edges [ ] [ ] , int values [ ] ) { ArrayList < Integer > adj [ ] = new ArrayList [ n ] ; for ( int i = 0 ; i < n ; i ++ ) adj [ i ] = new ArrayList < > ( ) ; for ( int i = 0 ; i < n - 1 ; i ++ ) { int u = edges [ i ] [ 0 ] - 1 ; int v = edges [ i ] [ 1 ] - 1 ; adj [ u ] . add ( v ) ; adj [ v ] . add ( u ) ; } int ans [ ] = new int [ n ] ; dfs ( 0 , - 1 , adj , ans , values ) ; for ( int x : ans ) { System . out . print ( x + " ▁ " ) ; } } public static void main ( String [ ] args ) { int N = 4 ; int edges [ ] [ ] = new int [ ] [ ] { { 1 , 2 } , { 1 , 3 } , { 3 , 4 } } ; int values [ ] = { 1 , - 1 , 0 , 1 } ; printAnswer ( N , edges , values ) ; } }