Maximize sum of MEX values of each node in an N | Function to create an N - ary Tree ; Traverse the edges ; Add edges ; Function to get the maximum sum of MEX values of tree rooted at 1 ; Initialize mex ; Iterate through all children of node ; Recursively find maximum sum of MEX values of each node in tree rooted at u ; Store the maximum sum of MEX of among all subtrees ; Increase the size of tree rooted at current node ; Resulting MEX for the current node of the recursive call ; Given N nodes ; Given N - 1 edges ; Stores the tree ; Generates the tree ; Returns maximum sum of MEX values of each node
function makeTree ( tree , edges , N ) { for ( var i = 0 ; i < N - 1 ; i ++ ) { var u = edges [ i ] [ 0 ] ; var v = edges [ i ] [ 1 ] ; tree [ u ] . push ( v ) ; } } function dfs ( node , tree ) { var mex = 0 ; var size = 1 ; tree [ node ] . forEach ( u => { var temp = dfs ( u , tree ) ; mex = Math . max ( mex , temp [ 0 ] ) ; size += temp [ 1 ] ; } ) ; return [ mex + size , size ] ; } var N = 7 ; var edges = [ [ 1 , 4 ] , [ 1 , 5 ] , [ 5 , 2 ] , [ 5 , 3 ] , [ 4 , 7 ] , [ 7 , 6 ] ] ; var tree = Array . from ( Array ( N + 1 ) , ( ) => Array ( ) ) ; makeTree ( tree , edges , N ) ; document . write ( dfs ( 1 , tree ) [ 0 ] ) ;