e-olymp
Соревнования

Dynamic programming on Trees - Top Level

Вершинное покрытие

Имеется невзвешенное неориентированное дерево. Найдите такое наименьшее подмножество вершин, что для любого ребра хотя бы один из его концов принадлежит этому множеству.

prb265.gif

Входные данные

Первая строка содержит количество вершин n (0 < n100000) в дереве. Следующие n - 1 строк задают n - 1 ребро дерева. Каждая строка содержит пару (u, v) означающую наличие ребра между вершинами u и v (1u, vn).

Выходные данные

Выведите количество вершин в искомом подмножестве.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
6
1 2
1 3
2 4
2 5
1 6
Выходные данные #1
2