4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура
Задача C. Марафон Канто
Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт
Скоро лето, Есмахан решил, что пора начать бегать по утрам в своем городе Канто. Город Канто представляет собой n перекрестков соединённых n−1 дорогой, где от любого перекрестка можно добраться до любого другого перекрестка двигаясь по дорогам. В планах было начать бегать с воскресенья, однако в этот же день был назначен городской ежегодный веломарафон Канто. Определим маршрут (a,b), что a<b, множеством дорог, которые лежат на кратчайшем пути между стартовым перекрестком a и конечным перекрестком b. Длиной маршрута (a,b) будем называть количество дорог по которым он проходит. Есмахан не хочет бегать по занятым дорогам веломарафона во время пробежки. На вход дается n количество перекрёстков в городе Канто. Далее дается n−1 дорога соединяющая два перекрестка. Гарантируется, что дается дороги таким образом, что от любого перекрестка можно добраться до любого другого перекрестка переходя только по дорогам. После дается q количество запросов на которые вы должны ответить. Запросы даются двух видов:
- x y, в нем вы должны ответить длиной самого длинного маршрута если веломарафон будет проходить через маршрут (x,y).
- k, в нем должны ответить количеством различных маршрутов (x,y), что Есмахан выберет маршрут длиной k.
Формат входного файла
Первая строка содержит одно целое число n (2<=n<=5∗105), обозначающее количество перекрестков в городе Канто.
В каждой из следующих n−1 строк содержится описание дорог: два целых числа u и v (1<=v,u<=n,u≠v).
Следующая строка содержит одно целое число q (1<=q<=5∗105), обозначающее количество запросов.
Следующие q строк содержат описания запросов.
Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса:
1 x y (1<=x<y<=n) для запросов первого типа.
2 k (0<=k<=n−1) для запросов второго типа.
Формат выходного файла
Для каждого запроса выведите ответ на него.
Система оценки
Данная задача содержит 10 подзадач, в которых выполняются следующие ограничения:
- Примеры из условия. Оценивается в 0 баллов.
- n<=1000. Гарантируется, что ui=i, vi=i+1 для всех i (1<=i<n). Оценивается в 8 баллов.
- Гарантируется, что ui=i, vi=i+1 для всех i (1<=i<n). Оценивается в 10 баллов.
- n,q<=500. Оценивается в 9 баллов.
- n,q<=3000. Оценивается в 11 баллов.
- Гарантируется, что все запросы 1-типа и xi=1 для всех i (1<=i<=q). Оценивается в 12 баллов.
- Гарантируется, что все запросы 1-типа. Оценивается в 12 баллов.
- q<=10. Оценивается в 11 баллов.
- ui=i+1,vi=⌊i+12⌋ для всех i (1<=i<n). Оценивается в 10 баллов.
- Исходные условия задачи. Оценивается в 17 баллов.
Пример:
Вход 8 1 2 2 3 2 4 3 5 1 6 4 7 7 8 6 2 3 1 4 6 1 1 8 2 4 1 2 3 2 2Ответ
4 2 2 6 5 12
Замечание
В первом запросе следущие четыре веломаршрута заставят Есмахана выбрать маршрут длины 3: (1, 3), (1, 5), (3, 6), (5, 6).
Во втором запросе два самых длинных маршрутов длины 2: (2, 5) и (4, 8).
В третьем запросе один самый длинный маршрут длины 2: (2, 5).
В четвертом запросе следущие шесть веломаршрутов заставят Есмахана выбрать маршрут длины
4: (2, 4), (2, 7), (2, 8), (4, 7), (4, 8), (7, 8).
В пятом запросе один самый длинный маршрут длинны 5: (6, 8).
В шестом запросе ответ 12.
(
Narkhan Kamzabek
)
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.