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
def dfs ( node , parent , tree , colour , answer ) : NEW_LINE INDENT answer [ node ] = colour [ node ] NEW_LINE for u in tree [ node ] : NEW_LINE INDENT if ( u == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT dfs ( u , node , tree , colour , answer ) NEW_LINE answer [ node ] += max ( answer [ u ] , 0 ) NEW_LINE DEDENT DEDENT def maxDiff ( tree , colour , N ) : NEW_LINE INDENT answer = [ 0 for _ in range ( N + 1 ) ] NEW_LINE dfs ( 1 , 0 , tree , colour , answer ) NEW_LINE high = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT high = max ( high , answer [ i ] ) NEW_LINE answer [ i ] = 0 NEW_LINE DEDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if colour [ i ] == - 1 : NEW_LINE INDENT colour [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT colour [ i ] = - 1 NEW_LINE DEDENT DEDENT dfs ( 1 , 0 , tree , colour , answer ) NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT high = max ( high , answer [ i ] ) NEW_LINE DEDENT return high NEW_LINE DEDENT N = 5 NEW_LINE tree = [ list ( ) for _ in range ( N + 1 ) ] NEW_LINE tree [ 1 ] . append ( 2 ) NEW_LINE tree [ 2 ] . append ( 1 ) NEW_LINE tree [ 1 ] . append ( 3 ) NEW_LINE tree [ 3 ] . append ( 1 ) NEW_LINE tree [ 2 ] . append ( 4 ) NEW_LINE tree [ 4 ] . append ( 2 ) NEW_LINE tree [ 3 ] . append ( 5 ) NEW_LINE tree [ 5 ] . append ( 3 ) NEW_LINE colour = [ 0 , 1 , 1 , - 1 , - 1 , 1 ] NEW_LINE print ( maxDiff ( tree , colour , N ) ) NEW_LINE