Sqrt ( or Square Root ) Decomposition | Set 2 ( LCA of Tree in O ( sqrt ( height ) ) time ) | Java program to find LCA using Sqrt decomposition ; block size = Math . sqrt ( height ) ; stores depth for each node ; stores first parent for each node ; stores first ancestor in previous block ; precalculating the required parameters associated with every node ; marking depth of cur node ; marking parent of cur node ; making jump_parent of cur node ; if it is first node of the block then its jump_parent is its cur parent ; if it is not the first node of this block then its jump_parent is jump_parent of its parent ; propogating the marking down the subtree ; using sqrt decomposition trick ; maintaining depth [ v ] > depth [ u ] ; climb to its jump parent ; u and v have same jump_parent ; precalclating 1 ) depth . 2 ) parent . 3 ) jump_parent for each node ; Driver code ; adding edges to the tree ; here we are directly taking height = 4 according to the given tree but we can pre - calculate height = max depth in one more dfs
import java . util . * ; class GFG { static final int MAXN = 1001 ; static int block_sz ; static int [ ] depth = new int [ MAXN ] ; static int [ ] parent = new int [ MAXN ] ; static int [ ] jump_parent = new int [ MAXN ] ; static Vector < Integer > [ ] adj = new Vector [ MAXN ] ; static void addEdge ( int u , int v ) { adj [ u ] . add ( v ) ; adj [ v ] . add ( u ) ; } static int LCANaive ( int u , int v ) { if ( u == v ) return u ; if ( depth [ u ] > depth [ v ] ) { int t = u ; u = v ; v = t ; } v = parent [ v ] ; return LCANaive ( u , v ) ; } static void dfs ( int cur , int prev ) { depth [ cur ] = depth [ prev ] + 1 ; parent [ cur ] = prev ; if ( depth [ cur ] % block_sz == 0 ) jump_parent [ cur ] = parent [ cur ] ; else jump_parent [ cur ] = jump_parent [ prev ] ; for ( int i = 0 ; i < adj [ cur ] . size ( ) ; ++ i ) if ( adj [ cur ] . get ( i ) != prev ) dfs ( adj [ cur ] . get ( i ) , cur ) ; } static int LCASQRT ( int u , int v ) { while ( jump_parent [ u ] != jump_parent [ v ] ) { if ( depth [ u ] > depth [ v ] ) { int t = u ; u = v ; v = t ; } v = jump_parent [ v ] ; } return LCANaive ( u , v ) ; } static void preprocess ( int height ) { block_sz = ( int ) Math . sqrt ( height ) ; depth [ 0 ] = - 1 ; dfs ( 1 , 0 ) ; } public static void main ( String [ ] args ) { for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 1 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 2 , 6 ) ; addEdge ( 3 , 7 ) ; addEdge ( 4 , 8 ) ; addEdge ( 4 , 9 ) ; addEdge ( 9 , 10 ) ; addEdge ( 9 , 11 ) ; addEdge ( 7 , 12 ) ; addEdge ( 7 , 13 ) ; int height = 4 ; preprocess ( height ) ; System . out . print ( " LCA ( 11,8 ) ▁ : ▁ " + LCASQRT ( 11 , 8 ) + "NEW_LINE"); System . out . print ( " LCA ( 3,13 ) ▁ : ▁ " + LCASQRT ( 3 , 13 ) + "NEW_LINE"); } }