Дано дерево из $$$n$$$ вершин и $$$(n-1)$$$ ребер. Изначально как ребра, так и вершины дерева являются непокрашенными. Вам доступна следующая операция: выбрать две вершины дерева и покрасить путь между ними (красятся как вершины, так и ребра на этом пути).
За какое минимальное число таких операций можно покрасить все дерево (все ребра и все вершины)?
В первой строке дано целое число $$$n$$$ ($$$2 \le n \le 200000$$$) — количество вершин в дереве.
В каждой из следующих $$$(n-1)$$$ строк даны два числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — вершины дерева, соединенные $$$i$$$-м ребром.
Выведите единственное целое число — минимальное количество операций, необходимое для покраски дерева.
5 1 2 1 3 1 4 1 5
2
5 1 2 2 3 3 4 4 5
1
4 1 2 3 2 4 2
2
Название |
---|