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

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

HotLog


 

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

(Время: 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
 A. Обед
 B. Страшный сон Егора
 C. Виталя и кубик
 D. Удаление чисел
 E. Юниты и ресурсы
 F. Задача без подвоха
 G. Раздел Империи
 H. Великая таблица умножения
 I. Индекс.Контест
 J. Юбилей
 K. Простая задача

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