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
thang040602:
20210516 19:10:01
i ACed this long ago and i just realized how weak the test set is :( 

princemishra:
20210118 15:28:40
https://www.youtube.com/watch?v=RuNAYVTn9qM&list=PLb3g_Z8nEv1j_BCfmZWHFe6jmU_zv8s&index=2


std_iostream:
20201010 23:33:19
Can someone please say how will be the output form for N=1? 

hack_010:
20200903 07:17:27
@osmanay2 Answer should be 5 in your test case. My solution got accepted with that. 

shameek:
20200616 03:49:14
2 states  the vertex number and a boolean used


kushagra_2:
20200422 19:52:18
First tree dp problem :) Indeed very happy to solve... A great problem worth solving!! 

danos:
20200321 08:20:56
13


sayamrak:
20200313 21:46:14
Simple Dp on trees 

osmanay2:
20200210 23:07:22
Test your solution with this case:


scolar_fuad:
20191201 05:26:35
Minimum vertex cover dp problem

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 