Find MEX of every subtree in given Tree | Stores the edges of the tree ; Function to add edges ; Function to merge two sorted vectors ; To store the result ; Iterating both vectors ; Pushing remaining elements of vector a ; Pushing remaining elements of vector b ; Function to perform the DFS Traversal that returns the subtree of node in sorted manner ; Iterate the childrens ; All values of subtree i in sorted manner ; Binary search to find MEX ; Find the mid ; Update the ranges ; Update the MEX for the current tree node ; Function to find MEX of each subtree of tree ; Function Call ; Printe the ans for each nodes ; Driver Code
let edges = [ ] ; function add_edge ( x , y ) { edges . push ( [ x , y ] ) ; } function merge ( a , b ) { let res = [ ] ; let i = 0 , j = 0 ; let n = a . length , m = b . length ; while ( i < n && j < m ) { if ( a [ i ] < b [ j ] ) res . push ( a [ i ++ ] ) ; else if ( b [ j ] < a [ i ] ) res . push ( b [ j ++ ] ) ; } while ( i < n ) res . push ( a [ i ++ ] ) ; while ( j < m ) res . push ( b [ j ++ ] ) ; return res ; } function help ( tree , x , p , c , sol ) { let res = [ ] ; res . push ( c [ x ] ) ; for ( let i of tree [ x ] ) { if ( i != p ) { let tmp = help ( tree , i , x , c , sol ) ; res = merge ( res , tmp ) ; } } let l = 0 , r = res . length - 1 ; let ans = res . length ; while ( l <= r ) { let mid = Math . floor ( ( l + r ) / 2 ) ; if ( res [ mid ] > mid ) r = mid - 1 ; else { ans = mid + 1 ; l = mid + 1 ; } } if ( res [ 0 ] != 0 ) ans = 0 ; sol [ x ] = ans ; return res ; } function solve ( A , C ) { let n = A ; let tree = new Array ( n + 1 ) . fill ( 0 ) . map ( ( ) => [ ] ) ; for ( let i of edges ) { tree [ i [ 0 ] ] . push ( i [ 1 ] ) ; tree [ i [ 1 ] ] . push ( i [ 0 ] ) ; } let sol = new Array ( n ) . fill ( 0 ) ; help ( tree , 0 , - 1 , C , sol ) ; for ( let i of sol ) document . write ( i + " " ) ; } let N = 6 ; add_edge ( 0 , 1 ) ; add_edge ( 1 , 2 ) ; add_edge ( 0 , 3 ) ; add_edge ( 3 , 4 ) ; add_edge ( 3 , 5 ) ; let val = [ 4 , 3 , 5 , 1 , 0 , 2 ] ; solve ( N , val ) ;