Hi, i was solving this problem, i think i am implementing a greedy algorithm, getting WA for this solution. The solution is self explanatory, i did a dfs on the tree to calculate level of each node and then printed the minimum of total number of node of same parity(odd/even), am i right doing this? asked 23 Sep '16, 20:16

This greedy solution is wrong. For example, imagine you have vertex 1 connected with vertex 2, and vertex 1 connected with 100 other vertices and vertex 2 connected with 100 other vertices. Obviously the correct answer is 2: we only include vertex 1 and 2, but your solution would print 101. Try to think of another greedy, or a dp. answered 24 Sep '16, 00:01

The problem with the greedy method has already been explained.Lets build a dynamic programming paradigm for it. Let, If we put a vertex in the set then we don't need to select any of its children, as we have covered all edges from this node to its children dp[i][1] = 1 + (for every child v of i > sum(min(dp[v][0] , dp[v][1])) answered 24 Sep '16, 00:41

@thedark, Your solution is correct but your interpretation is not. "If we put a vertex in the set then we don't need to select any of its children, as we have covered all edges from this node to its children" This is false. If we put a vertex in the set then we may or may not want to include some of its children. As you can see, you wrote dp[i][1] = 1+(sum(min(dp[v][0], dp[v][1])). Reflect on it. answered 06 Dec, 18:54
