Maximize sum of MEX values of each node in an N | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void makeTree ( vector < int > tree [ ] , pair < int , int > edges [ ] , int N ) { for ( int i = 0 ; i < N - 1 ; i ++ ) { int u = edges [ i ] . first ; int v = edges [ i ] . second ; tree [ u ] . push_back ( v ) ; } } pair < int , int > dfs ( int node , vector < int > tree [ ] ) { int mex = 0 ; int size = 1 ; for ( int u : tree [ node ] ) { pair < int , int > temp = dfs ( u , tree ) ; mex = max ( mex , temp . first ) ; size += temp . second ; } return { mex + size , size } ; } int main ( ) { int N = 7 ; pair < int , int > edges [ ] = { { 1 , 4 } , { 1 , 5 } , { 5 , 2 } , { 5 , 3 } , { 4 , 7 } , { 7 , 6 } } ; vector < int > tree [ N + 1 ] ; makeTree ( tree , edges , N ) ; cout << dfs ( 1 , tree ) . first ; return 0 ; }