Sqrt ( or Square Root ) Decomposition | Set 2 ( LCA of Tree in O ( sqrt ( height ) ) time ) | Python3 implementation to find LCA in a tree ; stores depth for each node ; stores first parent for each node ; marking parent for each node ; marking depth for each node ; propogating marking down the tree ; a dummy node ; precalculating 1 ) depth . 2 ) parent . for each node ; Time Complexity : O ( Height of tree ) recursively jumps one node above till both the nodes become equal ; Driver code ; adding edges to the tree
MAXN = 1001 NEW_LINE depth = [ 0 for i in range ( MAXN ) ] ; NEW_LINE parent = [ 0 for i in range ( MAXN ) ] ; NEW_LINE adj = [ [ ] for i in range ( MAXN ) ] NEW_LINE def addEdge ( u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) ; NEW_LINE adj [ v ] . append ( u ) ; NEW_LINE DEDENT def dfs ( cur , prev ) : NEW_LINE INDENT parent [ cur ] = prev ; NEW_LINE depth [ cur ] = depth [ prev ] + 1 ; NEW_LINE for i in range ( len ( adj [ cur ] ) ) : NEW_LINE INDENT if ( adj [ cur ] [ i ] != prev ) : NEW_LINE INDENT dfs ( adj [ cur ] [ i ] , cur ) ; NEW_LINE DEDENT DEDENT DEDENT def preprocess ( ) : NEW_LINE INDENT depth [ 0 ] = - 1 ; NEW_LINE dfs ( 1 , 0 ) ; NEW_LINE DEDENT def LCANaive ( u , v ) : NEW_LINE INDENT if ( u == v ) : NEW_LINE INDENT return u ; NEW_LINE DEDENT if ( depth [ u ] > depth [ v ] ) : NEW_LINE INDENT u , v = v , u NEW_LINE DEDENT v = parent [ v ] ; NEW_LINE return LCANaive ( u , v ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT addEdge ( 1 , 2 ) ; NEW_LINE addEdge ( 1 , 3 ) ; NEW_LINE addEdge ( 1 , 4 ) ; NEW_LINE addEdge ( 2 , 5 ) ; NEW_LINE addEdge ( 2 , 6 ) ; NEW_LINE addEdge ( 3 , 7 ) ; NEW_LINE addEdge ( 4 , 8 ) ; NEW_LINE addEdge ( 4 , 9 ) ; NEW_LINE addEdge ( 9 , 10 ) ; NEW_LINE addEdge ( 9 , 11 ) ; NEW_LINE addEdge ( 7 , 12 ) ; NEW_LINE addEdge ( 7 , 13 ) ; NEW_LINE preprocess ( ) ; NEW_LINE print ( ' LCA ( 11,8 ) ▁ : ▁ ' + str ( LCANaive ( 11 , 8 ) ) ) NEW_LINE print ( ' LCA ( 3,13 ) ▁ : ▁ ' + str ( LCANaive ( 3 , 13 ) ) ) NEW_LINE DEDENT