I am trying to solve this problem http://www.spoj.com/problems/PT07X/ understood the question but

unable to figure out an algorithm.Any one help me in solving the problem.

I am trying to solve this problem http://www.spoj.com/problems/PT07X/ understood the question but

unable to figure out an algorithm.Any one help me in solving the problem.

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.

- For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
- For each internal node:if any of its children is not selected, then select this node.DFS call at each child can be used to check this.