pre - compute the depth for each node and their first parent ( 2 ^ 0 th parent ) time complexity : O ( n )
void dfs ( int cur , int prev ) { depth [ cur ] = depth [ prev ] + 1 ; parent [ cur ] [ 0 ] = prev ; for ( int i = 0 ; i < tree [ cur ] . size ( ) ; i ++ ) { if ( tree [ cur ] [ i ] != prev ) dfs ( tree [ cur ] [ i ] , cur ) ; } }