Tree with small distances#10656
You are given an undirected tree consisting of vertices. An undirected tree is a connected 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 vertex to any other vertex is at most . Note that you are not allowed to add loops or 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 next n − 1 lines describe the edges: the -th edge is specified as a pair of vertices u_i, v_i\:(1 \le u_i, v_i \le n). It is guaranteed that the given graph is a tree. It is guaranteed that there are no loops or multiple edges among the given edges.
Print a single integer — the minimum number of edges that need to be added in order to ensure that the length of the shortest path from vertex to any other vertex does not exceed . Note that you cannot add loops or multiple edges.
Example 1
Example 2