| Codeforces Round 506 (Div. 3) |
|---|
| Закончено |
Задано неориентированное дерево, состоящее из $$$n$$$ вершин. Неориентированное дерево — это связный граф с $$$n - 1$$$ ребром.
Ваша задача — добавить минимальное количество ребер таким образом, что длина кратчайшего пути из вершины $$$1$$$ до любой другой вершины не превышает $$$2$$$. Заметьте, что вы не можете добавлять петли и кратные ребра.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.
Следующие $$$n - 1$$$ строк описывают ребра: ребро $$$i$$$ задано как пара вершин $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$). Гарантируется, что заданный граф является деревом. Гарантируется, что среди заданных ребер петли и кратные ребра отсутствуют.
Выведите одно целое число — минимальное количество ребер, которое необходимо добавить, чтобы длина кратчайшего пути из вершины $$$1$$$ до любой другой вершины не превышает $$$2$$$. Заметьте, что вы не можете добавлять петли и кратные ребра.
7
1 2
2 3
2 4
4 5
4 6
5 7
2
7
1 2
1 3
2 4
2 5
3 6
1 7
0
7
1 2
2 3
3 4
3 5
3 6
3 7
1
Дерево, соответствующее первому тестовому примеру: 
Ответ равен $$$2$$$, вот несколько возможных ответов: $$$[(1, 5), (1, 6)]$$$, $$$[(1, 4), (1, 7)]$$$, $$$[(1, 6), (1, 7)]$$$.
Дерево, соответствующее второму тестовому примеру: 
Ответ равен $$$0$$$.
Дерево, соответствующее третьему тестовому примеру: 
Ответ равен $$$1$$$, единственный способ достичь такого ответа — добавить ребро $$$(1, 3)$$$.
