Convert a tree to forest of even nodes | Return the number of nodes of subtree having node as a root . ; Mark node as visited . ; Traverse the adjacency list to find non - visited node . ; Finding number of nodes of the subtree of a subtree . ; If nodes are even , increment number of edges to removed . Else leave the node as child of subtree . ; Return the maximum number of edge to remove to make forest . ; Driver Code
def dfs ( tree , visit , ans , node ) : NEW_LINE INDENT num = 0 NEW_LINE temp = 0 NEW_LINE visit [ node ] = 1 NEW_LINE for i in range ( len ( tree [ node ] ) ) : NEW_LINE INDENT if ( visit [ tree [ node ] [ i ] ] == 0 ) : NEW_LINE INDENT temp = dfs ( tree , visit , ans , tree [ node ] [ i ] ) NEW_LINE if ( temp % 2 ) : NEW_LINE INDENT num += temp NEW_LINE DEDENT else : NEW_LINE INDENT ans [ 0 ] += 1 NEW_LINE DEDENT DEDENT DEDENT return num + 1 NEW_LINE DEDENT def minEdge ( tree , n ) : NEW_LINE INDENT visit = [ 0 ] * ( n + 2 ) NEW_LINE ans = [ 0 ] NEW_LINE dfs ( tree , visit , ans , 1 ) NEW_LINE return ans [ 0 ] NEW_LINE DEDENT N = 12 NEW_LINE n = 10 NEW_LINE tree = [ [ ] for i in range ( n + 2 ) ] NEW_LINE tree [ 1 ] . append ( 3 ) NEW_LINE tree [ 3 ] . append ( 1 ) NEW_LINE tree [ 1 ] . append ( 6 ) NEW_LINE tree [ 6 ] . append ( 1 ) NEW_LINE tree [ 1 ] . append ( 2 ) NEW_LINE tree [ 2 ] . append ( 1 ) NEW_LINE tree [ 3 ] . append ( 4 ) NEW_LINE tree [ 4 ] . append ( 3 ) NEW_LINE tree [ 6 ] . append ( 8 ) NEW_LINE tree [ 8 ] . append ( 6 ) NEW_LINE tree [ 2 ] . append ( 7 ) NEW_LINE tree [ 7 ] . append ( 2 ) NEW_LINE tree [ 2 ] . append ( 5 ) NEW_LINE tree [ 5 ] . append ( 2 ) NEW_LINE tree [ 4 ] . append ( 9 ) NEW_LINE tree [ 9 ] . append ( 4 ) NEW_LINE tree [ 4 ] . append ( 10 ) NEW_LINE tree [ 10 ] . append ( 4 ) NEW_LINE print ( minEdge ( tree , n ) ) NEW_LINE