Sub | Tree traversal to compute minimum difference ; Initial min difference is the color of node ; Traversing its children ; Not traversing the parent ; If the child is Adding positively to difference , we include it in the answer Otherwise , we leave the sub - tree and include 0 ( nothing ) in the answer ; DFS for colour difference : 1 colour - 2 colour ; Minimum colour difference is maximum answer value ; Clearing the current value to check for colour2 as well ; Interchanging the colours ; DFS for colour difference : 2 colour - 1 colour ; Checking if colour2 makes the minimum colour difference ; Nodes ; Adjacency list representation ; Edges ; Index represent the colour of that node There is no Node 0 , so we start from index 1 to N ; Printing the result
function dfs ( node , parent , tree , colour , answer ) { answer [ node ] = colour [ node ] ; for ( var u of tree [ node ] ) { if ( u == parent ) continue ; dfs ( u , node , tree , colour , answer ) ; answer [ node ] += Math . max ( answer [ u ] , 0 ) ; } } function maxDiff ( tree , colour , N ) { var answer = Array ( N + 1 ) . fill ( 0 ) ; dfs ( 1 , 0 , tree , colour , answer ) ; var high = 0 ; for ( var i = 1 ; i <= N ; i ++ ) { high = Math . max ( high , answer [ i ] ) ; answer [ i ] = 0 ; } for ( var i = 1 ; i <= N ; i ++ ) { if ( colour [ i ] == - 1 ) colour [ i ] = 1 ; else colour [ i ] = - 1 ; } dfs ( 1 , 0 , tree , colour , answer ) ; for ( var i = 1 ; i < N ; i ++ ) high = Math . max ( high , answer [ i ] ) ; return high ; } var N = 5 ; var tree = Array . from ( Array ( N + 1 ) , ( ) => Array ( ) ) ; tree [ 1 ] . push ( 2 ) ; tree [ 2 ] . push ( 1 ) ; tree [ 1 ] . push ( 3 ) ; tree [ 3 ] . push ( 1 ) ; tree [ 2 ] . push ( 4 ) ; tree [ 4 ] . push ( 2 ) ; tree [ 3 ] . push ( 5 ) ; tree [ 5 ] . push ( 3 ) ; var colour = [ 0 , 1 , 1 , - 1 , - 1 , 1 ] ; document . write ( maxDiff ( tree , colour , N ) ) ;