PT07X  Vertex Cover
You are given an unweighted, undirected tree. Write a program to find a vertex set of minimum size in this tree such that each edge has as least one of its endpoints in that set.
Input
The first line of the input file contains one integer N  number of nodes in the tree (0 < N <= 100000). Next N1 lines contain N1 edges of that tree  Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).
Output
Print number of nodes in the satisfied vertex set on one line.
Example 1
Input: 3 1 2 1 3 Output: 1 Explanation: The set can be {1}
Example 2
Input: 3 1 2 2 3 Output: 1 Explanation: The set can be {2}
hide comments
mzuenni:
20191129 12:32:36
just solve it greedy: take the neighbour of a leaf and remove it. 

sajalagrawal14:
20191109 05:53:13
nice question : dp on tree , pretty standard problem 

saurav_paul:
20190909 07:14:25
Accepted in first go. Dp + Dfs 

kumar18tushar:
20190531 09:34:13
dp+dfs worth solving !!! 

deepak097:
20190326 15:53:54
Indeed a good one :) 

paranoidninja:
20190211 20:05:36
Good problem to start off DP on trees 

ankitraj1996:
20190126 03:02:31
Why can not we use Bipartite checking? If anyone can explain, it would be helpful, I got a WA with that!


nitish235:
20190125 10:35:11
if you are applying greedy approach and getting WA then think about this case......


supriyanta:
20180803 01:51:04
DP on tree 

aman_sachin200:
20180615 12:30:21
Nice One!!DP+DFS!! 
Added by:  ThanhVy Hua 
Date:  20070328 
Time limit:  1s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Coauthor Amber 