Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Раздел Империи

(Время: 5 сек. Память: 64 Мб Сложность: 75%)

Великий император Виталиус Демидович вскоре уйдёт на покой. Во владениях он имеет империю, которая представляет из себя N стран, соединённых N - 1 дорогой так, что из каждой страны есть путь в любую другую.

Придворный оракул императора рассказал, что некоторые страны могут ослабеть и исчезнуть с лица Земли. Теперь Виталиус не находит покоя. Ведь если некоторые страны исчезнут, то империя может распасться на несколько новых. А именно, после исчезновения страны вслед за ней исчезают и все дороги, которые к ней примыкали. Все оставшиеся страны объединяются по новым империям по следующему правилу: если две страны всё ещё достижимы друг от друга по оставшимся дорогам, то они будут находиться в одной империи.

Император беспокоится о величии новых империй, а именно его интересует размер наибольшей из образовавшихся империй после удаления некоторых стран. Придворный картограф Виталиуса, то есть Вы, теперь завален запросами для некоторых множеств стран. Для каждого такого множества вычислите наибольший размер новой империи, если заданные страны исчезнут.

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

В первой строке входного файла INPUT.TXT содержится целое число N — размер империи (1 ≤ N ≤ 200 000).

В следующих N - 1 строках содержится по паре чисел ai и bi означающих, что соответствующие страны соединены дорогой (1 ≤ ai, bi ≤ N; ai ≠ bi).

Далее записано целое число M — количество запросов (1 ≤ M ≤ 500 000).

В следующих M строках идёт описание запросов. Каждый запрос содержится в отдельной строке и начинается с целого числа k, следом за которым идут k целых различных чисел vi — номера стран для удаления (1 ≤ k, vi ≤ N).

Гарантируется, что сумма всех k в одном тесте не превосходит 500 000.

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

В выходной файл OUTPUT.TXT выведите M целых чисел — для каждого множества стран в отдельной строке выведите максимальный размер новой империи.

Пример

INPUT.TXTOUTPUT.TXT
114
1 2
1 3
2 6
2 7
3 4
3 5
6 8
8 9
8 10
7 11
7 12
7 13
12 14
4
1 2
3 1 7 8
4 2 3 8 12
4 9 10 14 5
5
3
3
10

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2021 / 2022
 2022 / 2023
 A. Обед
 B. Страшный сон Егора
 C. Виталя и кубик
 D. Удаление чисел
 E. Юниты и ресурсы
 F. Задача без подвоха
 G. Раздел Империи
 H. Великая таблица умножения
 I. Индекс.Контест
 J. Юбилей
 K. Простая задача

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru