4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Задача C. Марафон Канто

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Скоро лето, Есмахан решил, что пора начать бегать по утрам в своем городе Канто. Город Канто представляет собой $n$ перекрестков соединённых $n - 1$ дорогой, где от любого перекрестка можно добраться до любого другого перекрестка двигаясь по дорогам. В планах было начать бегать с воскресенья, однако в этот же день был назначен городской ежегодный веломарафон Канто. Определим маршрут $(a,b)$, что $a < b$, множеством дорог, которые лежат на кратчайшем пути между стартовым перекрестком $a$ и конечным перекрестком $b$. Длиной маршрута $(a,b)$ будем называть количество дорог по которым он проходит. Есмахан не хочет бегать по занятым дорогам веломарафона во время пробежки. На вход дается $n$ количество перекрёстков в городе Канто. Далее дается $n - 1$ дорога соединяющая два перекрестка. Гарантируется, что дается дороги таким образом, что от любого перекрестка можно добраться до любого другого перекрестка переходя только по дорогам. После дается $q$ количество запросов на которые вы должны ответить. Запросы даются двух видов:

1. $x$ $y$, в нем вы должны ответить длиной самого длинного маршрута если веломарафон будет проходить через маршрут $(x, y)$.
2. $k$, в нем должны ответить количеством различных маршрутов $(x, y)$, что Есмахан выберет маршрут длиной $k$.

Выведите ответ на каждый запрос. Поэтому хочет выяснить длину самого длинного маршрута $(u, v)$ который будет проходить по свободным дорогам от веломарафона маршрутом $(x, y)$, чтобы его пробежка была максимальна. Так же, Есмахан хочет выяснить сколько возможных маршрутов $(x, y)$ веломарафона возможно, что его пробежке будет длины $k$?

Формат входного файла

Первая строка содержит одно целое число $n$ ($2 <= n <= 5*10^5$), обозначающее количество перекрестков в городе Канто. В каждой из следующих $n-1$ строк содержится описание дорог: два целых числа $u$ и $v$ $(1 <= v,u <= n, u \ne v)$. Следующая строка содержит одно целое число $q$ ($1 <= q <= 5*10^5$), обозначающее количество запросов. Следующие $q$ строк содержат описания запросов. Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса: $1$ $x$ $y$ $(1 <= x < y <= n)$ для запросов первого типа. $2$ $k$ $(0 <= k <= n - 1$) для запросов второго типа.

Формат выходного файла

Для каждого запроса выведите ответ на него.

Система оценки

Данная задача содержит $10$ подзадач, в которых выполняются следующие ограничения:

1. Примеры из условия. Оценивается в $0$ баллов.
2. $n <= 1000$. Гарантируется, что $u_i=i$, $v_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $8$ баллов.
3. Гарантируется, что $u_i=i$, $v_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $10$ баллов.
4. $n, q <= 500$. Оценивается в $9$ баллов.
5. $n, q <= 3000$. Оценивается в $11$ баллов.
6. Гарантируется, что все запросы 1-типа и $x_i = 1$ для всех $i$ ($1 <= i <= q$). Оценивается в $12$ баллов.
7. Гарантируется, что все запросы 1-типа. Оценивается в $12$ баллов.
8. $q <= 10$. Оценивается в $11$ баллов.
9. $u_i=i+1, v_i=\lfloor \frac{i+1}{2} \rfloor$ для всех $i$ $(1 <= i < n$). Оценивается в $10$ баллов.
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 )