Disjoint Set Union on trees | Set 1 | Python3 code to find maximum subtree such that all nodes are even in weight ; Structure for Edge ; ' id ' : stores parent of a node . ' sz ' : stores size of a DSU tree . ; Function to assign root ; Function to find Union ; Utility function for Union ; Edge between ' u ' and 'v ; 0 - indexed nodes ; If weights of both ' u ' and ' v ' are even then we make union of them . ; Function to find maximum size of DSU tree ; Driver code ; Weights of nodes ; Number of nodes in a tree ; Initializing every node as a tree with single node . ; Find maximum size of DSU tree .
N = 100010 NEW_LINE class Edge : NEW_LINE INDENT def __init__ ( self , u , v ) : NEW_LINE INDENT self . u = u NEW_LINE self . v = v NEW_LINE DEDENT DEDENT id = [ 0 for i in range ( N ) ] NEW_LINE sz = [ 0 for i in range ( N ) ] ; NEW_LINE def Root ( idx ) : NEW_LINE INDENT i = idx ; NEW_LINE while ( i != id [ i ] ) : NEW_LINE INDENT id [ i ] = id [ id [ i ] ] NEW_LINE i = id [ i ] ; NEW_LINE DEDENT return i ; NEW_LINE DEDENT def Union ( a , b ) : NEW_LINE INDENT i = Root ( a ) NEW_LINE j = Root ( b ) ; NEW_LINE if ( i != j ) : NEW_LINE INDENT if ( sz [ i ] >= sz [ j ] ) : NEW_LINE INDENT id [ j ] = i NEW_LINE sz [ i ] += sz [ j ] ; NEW_LINE sz [ j ] = 0 ; NEW_LINE DEDENT else : NEW_LINE INDENT id [ i ] = j NEW_LINE sz [ j ] += sz [ i ] ; NEW_LINE sz [ i ] = 0 ; NEW_LINE DEDENT DEDENT DEDENT def UnionUtil ( e , W , q ) : NEW_LINE INDENT for i in range ( q ) : NEW_LINE DEDENT ' NEW_LINE INDENT u = e [ i ] . u NEW_LINE v = e [ i ] . v NEW_LINE u -= 1 NEW_LINE v -= 1 NEW_LINE if ( W [ u ] % 2 == 0 and W [ v ] % 2 == 0 ) : NEW_LINE INDENT Union ( u , v ) ; NEW_LINE DEDENT DEDENT def findMax ( n , W ) : NEW_LINE INDENT maxi = 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( W [ i ] % 2 == 0 ) : NEW_LINE INDENT maxi = max ( maxi , sz [ i ] ) ; NEW_LINE DEDENT DEDENT return maxi ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT W = [ 1 , 2 , 6 , 4 , 2 , 0 , 3 ] NEW_LINE n = len ( W ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT id [ i ] = i NEW_LINE sz [ i ] = 1 ; NEW_LINE DEDENT e = [ Edge ( 1 , 2 ) , Edge ( 1 , 3 ) , Edge ( 2 , 4 ) , Edge ( 2 , 5 ) , Edge ( 4 , 6 ) , Edge ( 6 , 7 ) ] NEW_LINE q = len ( e ) NEW_LINE UnionUtil ( e , W , q ) ; NEW_LINE maxi = findMax ( n , W ) ; NEW_LINE print ( " Maximum ▁ size ▁ of ▁ the ▁ subtree ▁ with ▁ " , end = ' ' ) ; NEW_LINE print ( " even ▁ weighted ▁ nodes ▁ = " , maxi ) ; NEW_LINE DEDENT