Disjoint Set Union on trees | Set 1 | Javascript code to find maximum subtree such that all nodes are even in weight ; ' 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 ; Weights of nodes ; Number of nodes in a tree ; Initializing every node as a tree with single node . ; Find maximum size of DSU tree .
let N = 100010 ; let id = new Array ( N ) ; let sz = new Array ( N ) ; function Root ( idx ) { let i = idx ; while ( i != id [ i ] ) { id [ i ] = id [ id [ i ] ] ; i = id [ i ] ; } return i ; } function Union ( a , b ) { let i = Root ( a ) , j = Root ( b ) ; if ( i != j ) { if ( sz [ i ] >= sz [ j ] ) { id [ j ] = i ; sz [ i ] += sz [ j ] ; sz [ j ] = 0 ; } else { id [ i ] = j ; sz [ j ] += sz [ i ] ; sz [ i ] = 0 ; } } } function UnionUtil ( e , W , q ) { for ( let i = 0 ; i < q ; i ++ ) { let u , v ; u = e [ i ] [ 0 ] ; v = e [ i ] [ 1 ] ; u -- ; v -- ; if ( W [ u ] % 2 == 0 && W [ v ] % 2 == 0 ) Union ( u , v ) ; } } function findMax ( n , W ) { let maxi = 0 ; for ( let i = 1 ; i < n ; i ++ ) if ( W [ i ] % 2 == 0 ) maxi = Math . max ( maxi , sz [ i ] ) ; return maxi ; } let W = [ 1 , 2 , 6 , 4 , 2 , 0 , 3 ] ; let n = W . length ; for ( let i = 0 ; i < n ; i ++ ) { id [ i ] = i ; sz [ i ] = 1 ; } let e = [ [ 1 , 2 ] , [ 1 , 3 ] , [ 2 , 4 ] , [ 2 , 5 ] , [ 4 , 6 ] , [ 6 , 7 ] ] ; let q = e . length ; UnionUtil ( e , W , q ) ; let maxi = findMax ( n , W ) ; document . write ( " " ) ; document . write ( " " + maxi ) ;