IOI Preparation - Trees
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 end-points in that set.
The first line contains one integer n (0 < n ≤ 100000) – number of nodes in the tree. Next n - 1 lines contain n - 1 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).
Print number of nodes in the satisfied vertex set on one line.
6 1 2 1 3 2 4 2 5 1 6