Find MEX of every subtree in given Tree | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < int > > edges ; void add_edge ( int x , int y ) { edges . push_back ( { x , y } ) ; } vector < int > merge ( vector < int > & a , vector < int > & b ) { vector < int > res ; int i = 0 , j = 0 ; int n = a . size ( ) , m = b . size ( ) ; while ( i < n && j < m ) { if ( a [ i ] < b [ j ] ) res . push_back ( a [ i ++ ] ) ; else if ( b [ j ] < a [ i ] ) res . push_back ( b [ j ++ ] ) ; } while ( i < n ) res . push_back ( a [ i ++ ] ) ; while ( j < m ) res . push_back ( b [ j ++ ] ) ; return res ; } vector < int > help ( vector < int > tree [ ] , int x , int p , vector < int > & c , vector < int > & sol ) { vector < int > res ; res . push_back ( c [ x ] ) ; for ( auto i : tree [ x ] ) { if ( i != p ) { vector < int > tmp = help ( tree , i , x , c , sol ) ; res = merge ( res , tmp ) ; } } int l = 0 , r = res . size ( ) - 1 ; int ans = res . size ( ) ; while ( l <= r ) { int mid = ( 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 ; } void solve ( int A , vector < int > C ) { int n = A ; vector < int > tree [ n + 1 ] ; for ( auto i : edges ) { tree [ i [ 0 ] ] . push_back ( i [ 1 ] ) ; tree [ i [ 1 ] ] . push_back ( i [ 0 ] ) ; } vector < int > sol ( n , 0 ) ; help ( tree , 0 , -1 , C , sol ) ; for ( auto i : sol ) cout << i << " ▁ " ; } int main ( ) { int N = 6 ; add_edge ( 0 , 1 ) ; add_edge ( 1 , 2 ) ; add_edge ( 0 , 3 ) ; add_edge ( 3 , 4 ) ; add_edge ( 3 , 5 ) ; vector < int > val = { 4 , 3 , 5 , 1 , 0 , 2 } ; solve ( N , val ) ; return 0 ; }