eolymp
bolt
Try our new interface for solving problems
Məsələlər

Расстояние на дереве

Расстояние на дереве

Задано неориентированное дерево \textbf{T}. Пусть \textbf{S }- множество всех целых чисел \textbf{x }таких, что существует два различных листа \textbf{u }и \textbf{v }в \textbf{T}, удовлетворяющих \textbf{d}(\textbf{u},\textbf{ v}) = \textbf{x}. Через \textbf{d}(\textbf{u},\textbf{ v}) обозначено количество ребер в кратчайшем пути между \textbf{u }и \textbf{v}. Найдите множество \textbf{S}. \InputFile Первая строка содержит количество вершин \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{200000}) в дереве. Каждая из следующих \textbf{n - 1 }строк содержит два числа \textbf{x }и \textbf{y }(\textbf{1} ≤ \textbf{x}, \textbf{y} ≤ \textbf{n}): номера вершин, соединенных ребром. Гарантируется, что заданный граф является деревом. \OutputFile В первой строке вывести количество элементов в \textbf{S}. Далее следует вывести все элементы \textbf{S} в возрастающем порядке, по одному в строке.
Zaman məhdudiyyəti 6 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3
1 2
3 2
Çıxış verilənləri #1
1
2
Mənbə 2013 Петрозаводск, MIPT contest, Август 25, Задача J