Республиканская олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Марафон Канто

Скоро лето, Есмахан решил, что пора начать бегать по утрам в своем городе Канто. Город Канто представляет собой $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$ $(1 \leq n \leq 5 * 10^5)$, обозначающее количество перекрестков в городе Канто.

В каждой из следующих $n − 1$ строк содержится описание дорог: два целых числа $u$ и $v(1 \leq v, u \leq n, u \neq v)$.

Следующая строка содержит одно целое число $q (1 \leq q \leq 5 * 10^5)$, обозначающее количество запросов.

Следующие $q$ строк содержат описания запросов.

Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса:

$1 x y (1 \leq x, y \leq n)$ для запросов первого типа.

$2 k (0 \leq k \leq n − 1)$ для запросов второго типа.

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

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

Примеры

Ввод

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