Largest subtree sum for each vertex of given N | 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 ; Given nodes ; Give N edges ; Given values ; Function Call
function dfs ( v , p , adj , ans , vals ) { let isLeaf = true ; ans [ v ] = Number . MIN_VALUE ; for ( let u = 0 ; u < adj [ v ] . length ; u ++ ) { if ( adj [ v ] [ u ] == p ) continue ; isLeaf = false ; dfs ( adj [ v ] [ u ] , v , adj , ans , vals ) ; ans [ v ] = Math . max ( ans [ adj [ v ] [ u ] ] + vals [ v ] , Math . max ( ans [ adj [ v ] [ u ] ] , vals [ adj [ v ] [ u ] ] ) ) ; } if ( isLeaf ) { ans [ v ] = vals [ v ] ; } } function printAnswer ( n , edges , values ) { let adj = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) adj [ i ] = [ ] ; for ( let i = 0 ; i < n - 1 ; i ++ ) { let u = edges [ i ] [ 0 ] - 1 ; let v = edges [ i ] [ 1 ] - 1 ; adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } let ans = new Array ( n ) ; dfs ( 0 , - 1 , adj , ans , values ) ; for ( let x = 0 ; x < ans . length ; x ++ ) { document . write ( ans [ x ] + " " ) ; } } let N = 4 ; let edges = [ [ 1 , 2 ] , [ 1 , 3 ] , [ 3 , 4 ] ] ; let values = [ 1 , - 1 , 0 , 1 ] ; printAnswer ( N , edges , values ) ;