You are given a tree(a simple connected graph with no cycles). The tree has N nodes numbered from 1 to N and is rooted at node 1.
Find the maximum number of edges you can remove from the tree to get a forest such that each connected component of the forest contains an even number of nodes.
Constraints 2 <= 2 <= 100
Note: The tree input will be such that it can always be decomposed into components containing an even number of nodes.
|
DFS traversal |
2 1 |
DFS traversal
2 1 3 1 4 3 5 2 6 1 7 2 8 6 9 8 10 8 On removing edges (1,3) and (1,6), we can get the desired result 2.