E. Innopolis Data Center
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В дата-центре Университета Иннополис есть $$$n$$$ серверов, занумерованных последовательными целыми числами от $$$1$$$ до $$$n$$$. Сервера соединены $$$n - 1$$$ оптоволоконными кабелями таким образом, что между любыми двумя серверами возможна передача данных по одному или нескольким кабелям, иными словами, связи между серверами образуют дерево.

Каждый оптоволоконный кабель передает данные с задержкой в $$$1$$$ единицу времени, а задержка между двумя серверами равна расстоянию в дереве между этими серверами.

Требуется выбрать несколько серверов для системы распределенного хранения данных таким образом, чтобы задержка между любыми двумя серверами, входящими в систему, не превышала $$$d$$$. Пусть выбраны сервера $$$s_1, s_2, \ldots, s_k$$$, тогда общая задержка системы равна сумме задержек между всеми $$$\frac{k (k - 1)}{2}$$$ парами серверов $$$s_i$$$. Формально:

  1. должно выполняться $$$\mathtt{dist}(s_i, s_j) \le d$$$ для любых $$$i$$$ и $$$j$$$ (где $$$\mathtt{dist}$$$ — расстояние в дереве);
  2. и тогда общая задержка системы равна $$$\sum\limits_{i \lt j} \mathtt{dist}(s_i, s_j)$$$.

Ваша задача — ответить на $$$q$$$ запросов. Каждый запрос задается номером одного сервера $$$u$$$ и состоит в следующем: в случае, если конкретный сервер $$$u$$$ будет включен в систему хранения данных, какова будет максимальная возможная общая задержка системы?

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$d$$$ — количество серверов в дата-центре и максимальная разрешенная задержка между двумя серверами ($$$2 \le n \le 5 \cdot 10^5$$$; $$$0 \le d \le n - 1$$$).

Каждая из следующих $$$n - 1$$$ строк содержит по два целых числа $$$a_i$$$ и $$$b_i$$$ — номера двух серверов, соединенных $$$i$$$-м оптическим кабелем напрямую ($$$1 \le a_i, b_i \le n$$$). Гарантируется, что между любыми двумя серверами существует возможность передать данные по одному или нескольким последовательным кабелям.

Следующая строка содержит одно целое число $$$q$$$ — количество запросов ($$$1 \le q \le 10$$$). В $$$i$$$-й из следующих $$$q$$$ строк дано единственное целое число $$$u_i$$$ — номер сервера из $$$i$$$-го запроса ($$$1 \le u_i \le n$$$).

Выходные данные

Для каждого запроса выведите в отдельной строке одно целое число — максимальную общую задержку системы в случае, когда соответствующий сервер входит в систему хранения данных.

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

Баллы за каждую подзадачу с 1 по 4 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Каждый тест в подзадачах 5 и 6 оценивается независимо и стоит 3 балла в подзадаче 5 или 2 балла в подзадаче 6.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
0–примеры из условияполная
112$$$n \le 15$$$0первая ошибка
211$$$d = n - 1$$$первая ошибка
313$$$n \le 300$$$0, 1первая ошибка
416$$$n \le 5000$$$0, 1, 3первая ошибка
5$$$8 \times 3$$$$$$n \le 10^5$$$0, 1, 3, 4полная
6$$$12 \times 2$$$без дополнительных ограничений0 – 6полная
Примеры
Входные данные
7 2
2 1
1 3
2 4
5 4
4 7
6 5
7
7
6
5
4
3
2
1
Выходные данные
9
4
9
9
4
9
4
Входные данные
2 0
1 2
1
1
Выходные данные
0
Примечание

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

  • для сервера $$$1$$$ — множество $$$\{1, 2, 3\}$$$ или $$$\{1, 2, 4\}$$$;
  • для серверов $$$2$$$, $$$4$$$, $$$5$$$ и $$$7$$$ — множество $$$\{2, 4, 5, 7\}$$$;
  • для сервера $$$3$$$ — $$$\{1, 2, 3\}$$$;
  • для сервера $$$6$$$ — $$$\{4, 5, 6\}$$$.