Tree with Small Distances
Contest: Codeforces Round 506 (Div. 3)
Difficulty rating: 2100
Tags: 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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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)$$$.

Example input:
7
1 2
2 3
2 4
4 5
4 6
5 7

Example output:
2

Example input:
7
1 2
1 3
2 4
2 5
3 6
1 7

Example output:
0

Editorial:
The first idea is the following: it is always profitable to add the edges from the vertex $$$1$$$ to any other vertex. The proof is the following: if we will add two edges $$$(1, u)$$$ and $$$(u, v)$$$ then the distance to the vertex $$$u$$$ will be $$$1$$$, the distance to the vertex $$$v$$$ will be $$$2$$$. But we can add edges $$$(1, u)$$$ and $$$(1, v)$$$ and this will be better (in fact, you cannot obtain the less answer by adding two edges in the other way).
The main idea is the following. Let's carry all vertices of the tree with the distance more than $$$2$$$ in the set. Let the vertex with the maximum distance be $$$v$$$. What we will obtain if we will add the edge $$$(1, v)$$$? The distance to the vertex $$$v$$$ will be $$$1$$$ and the distance to the vertex $$$p_v$$$ (where $$$p_v$$$ is the parent of the vertex $$$v$$$ if we will root the tree by the vertex $$$1$$$) will be $$$2$$$. So we will make reachable at most two vertices (if the vertex $$$p_v$$$ is already reachable then it will be not counted in the answer). Now what we will obtain if we will add the edge $$$(1, p_v)$$$? We will make reachable all the vertices adjacent to the vertex $$$p_v$$$ and the vertex $$$p_v$$$ (the number of such vertices is not less than $$$1$$$ so this move won't make the answer greater instead of any other way to add the edge). After adding such edge let's remove the vertex $$$p_v$$$ and all vertices adjacent to it from the set. We need to repeat this algorithm until the set will not become empty.
Time complexity is $$$O(n \log n)$$$.
I sure that there exists the solution with the dynamic programming in the linear time, I will be very happy if someone will explain it to other participants.