Задачи
Дерево коротких расстояний
Дерево коротких расстояний
Задано неориентированное дерево, состоящее из $n$ вершин. Неориентированное дерево --- это связный граф с $n − 1$ ребром.
Ваша задача --- добавить минимальное количество ребер таким образом, чтобы длина кратчайшего пути из вершины $1$ до любой другой вершины не превышала $2$. Заметьте, что Вы не можете добавлять петли и кратные ребра.
\InputFile
Первая строка содержит одно целое число $n\:(2 \le n \le 2 \cdot 10^5)$ --- количество вершин в дереве.
Следующие $n − 1$ строк описывают ребра: ребро $i$ задано как пара вершин $u_i, v_i\:(1 \le u_i, v_i \le n)$. Гарантируется, что заданный граф является деревом. Гарантируется, что среди заданных ребер петли и кратные ребра отсутствуют.
\OutputFile
Выведите одно целое число — минимальное количество ребер, которое необходимо добавить, чтобы длина кратчайшего пути из вершины $1$ до любой другой вершины не превышает $2$. Заметьте, что вы не можете добавлять петли и кратные ребра.
\includegraphics{https://static.e-olymp.com/content/ba/bab3f0a5d883f8af999f2242f931f02ea7ec5b9b.gif}
Входные данные #1
7 1 2 2 3 2 4 4 5 4 6 5 7
Выходные данные #1
2
Входные данные #2
7 1 2 1 3 2 4 2 5 3 6 1 7
Выходные данные #2
0