Codeforces Round 633 (Div. 1) |
---|
Закончено |
У вас есть дерево из $$$n$$$ вершин. Вы собираетесь преобразовать это дерево в $$$n$$$ резинок на бесконечной плоскости. Должно выполняться следующее;
Теперь давайте дадим следующие определения:
Можно доказать, что при заданных ограничениях существует преобразование и последовательность вложенных резинок.
Какую максимальную длину последовательности вложенных резинок можно получить из данного дерева? Найдите и выведите ее.
Первая строка содержит целое число $$$n$$$ ($$$3 \le n \le 10^{5}$$$) — количество вершин в данном дереве.
$$$i$$$-я из следующих $$$n-1$$$ строк содержит два целых числа $$$a_{i}$$$ и $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$) — это означает, что существует ребро между $$$a_{i}$$$ и $$$b_{i}$$$. Гарантируется, что данный граф образует дерево из $$$n$$$ вершин.
Выведите ответ.
6 1 3 2 3 3 4 4 5 4 6
4
4 1 2 2 3 3 4
2
В первом примере можно получить вложенную последовательность из $$$4$$$ резинок ($$$1$$$, $$$2$$$, $$$5$$$ и $$$6$$$) с помощью следующего преобразования, приведенного ниже. Конечно, существуют и другие преобразования для создания вложенной последовательности длины $$$4$$$. Однако вы не можете сделать последовательность из $$$5$$$ или более вложенных резинок для данного дерева.
Одно из возможных преобразований для второго примера приведено ниже.
Название |
---|