E. Tree with Small Distances
dp; graphs; greedy
You are given an undirected tree consisting of \(n\) vertices. An undirected tree is a connected undirected graph with \(n - 1\) edges.Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex \(1\) to any other vertex is at most \(2\). Note that you are not allowed to add loops and multiple edges.
The first line contains one integer \(n\) (\(2 \le n \le 2 \cdot 10^5\)) — the number of vertices in the tree.The following \(n - 1\) lines contain edges: edge \(i\) is given as a pair of vertices \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)). It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.
Print a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex \(1\) to any other vertex at most \(2\). Note that you are not allowed to add loops and multiple edges.
The tree corresponding to the first example: The answer is \(2\), some of the possible answers are the following: \([(1, 5), (1, 6)]\), \([(1, 4), (1, 7)]\), \([(1, 6), (1, 7)]\).The tree corresponding to the second example: The answer is \(0\).The tree corresponding to the third example: The answer is \(1\), only one possible way to reach it is to add the edge \((1, 3)\).