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 ; Driver Code ; Given N nodes ; Given N - 1 edges ; Stores the tree ; Generates the tree ; Returns maximum sum of MEX values of each node
def makeTree ( tree , edges , N ) : NEW_LINE INDENT for i in range ( N - 1 ) : NEW_LINE INDENT u = edges [ i ] [ 0 ] NEW_LINE v = edges [ i ] [ 1 ] NEW_LINE tree [ u ] . append ( v ) NEW_LINE DEDENT return tree NEW_LINE DEDENT def dfs ( node , tree ) : NEW_LINE INDENT mex = 0 NEW_LINE size = 1 NEW_LINE for u in tree [ node ] : NEW_LINE INDENT temp = dfs ( u , tree ) NEW_LINE mex = max ( mex , temp [ 0 ] ) NEW_LINE size += temp [ 1 ] NEW_LINE DEDENT return [ mex + size , size ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 7 NEW_LINE edges = [ [ 1 , 4 ] , [ 1 , 5 ] , [ 5 , 2 ] , [ 5 , 3 ] , [ 4 , 7 ] , [ 7 , 6 ] ] NEW_LINE tree = [ [ ] for i in range ( N + 1 ) ] NEW_LINE tree = makeTree ( tree , edges , N ) NEW_LINE print ( dfs ( 1 , tree ) [ 0 ] ) NEW_LINE DEDENT