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
d_skyhawk:
20170401 06:45:04
DP+Tree=AC in a go 

rishi_07:
20170331 15:48:01
Finally AC! Nice DP. 

cake_is_a_lie:
20170305 14:44:08
For some reason I understood each vertex needed one neighbour in the output set. That cost me SO many WAs. 

siddharth9820:
20170219 09:27:54
Isnt it a straight divide and conquer problem? 

sina_ss:
20170214 18:03:23
it is so badihi Last edit: 20170214 18:53:24 

vengatesh15:
20161223 06:50:41
AC in 1 go :) 

lt:
20161127 14:51:55
Greedy is failing in very particular cases, while DP is awesome! :D Last edit: 20161127 14:52:50 

kartikay singh:
20160630 18:05:47
Tried with dp,greedy and maximum matching ... :D 

Md. Najim Ahmed:
20160215 06:33:23
Excellent practice problem. Topics: Minimum dominating set in a tree.


bholagabbar:
20151207 17:11:25
To solve it using Maximum matching:

Added by:  ThanhVy Hua 
Date:  20070328 
Time limit:  0.194s1.254s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Coauthor Amber 