Maximize sum of MEX values of each node in an N | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void makeTree ( Vector < Integer > tree [ ] , pair edges [ ] , int N ) { for ( int i = 0 ; i < N - 1 ; i ++ ) { int u = edges [ i ] . first ; int v = edges [ i ] . second ; tree [ u ] . add ( v ) ; } } static pair dfs ( int node , Vector < Integer > tree [ ] ) { int mex = 0 ; int size = 1 ; for ( int u : tree [ node ] ) { pair temp = dfs ( u , tree ) ; mex = Math . max ( mex , temp . first ) ; size += temp . second ; } return new pair ( mex + size , size ) ; } public static void main ( String [ ] args ) { int N = 7 ; pair edges [ ] = { new pair ( 1 , 4 ) , new pair ( 1 , 5 ) , new pair ( 5 , 2 ) , new pair ( 5 , 3 ) , new pair ( 4 , 7 ) , new pair ( 7 , 6 ) } ; @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] tree = new Vector [ N + 1 ] ; for ( int i = 0 ; i < tree . length ; i ++ ) tree [ i ] = new Vector < Integer > ( ) ; makeTree ( tree , edges , N ) ; System . out . print ( ( dfs ( 1 , tree ) . first ) ) ; } }