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

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


 

Локдаун Империи

(Время: 3 сек. Память: 256 Мб Сложность: 65%)

Империя состоит из n городов, соединёнными n−1 двусторонними дорогами так, что из любого города можно добраться до любого другого.

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

Всего есть m сценариев, каждый из которых подразумевает закрытие городов с номерами от l до r (включительно) на карантин.

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

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

Первая строка входного файла INPUT.TXT содержит целое число n — количество городов (1 ≤ n ≤ 2×105). В следующих n−1 строках содержатся пары чисел ai и bi, означающих, что между этими городами проложена дорога (1 ≤ ai, bi ≤ n). Следующая строка содержит целое число m — количество сценариев (1 ≤ m ≤ 2×105). В следующих m строках содержатся пары чисел li и ri (1 ≤ li ≤ ri ≤ n).

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

В выходной файл OUTPUT.TXT на каждый сценарий выведите ответ в отдельной строке.

Пример

INPUT.TXTOUTPUT.TXT
16
3 4
3 5
4 6
1 6
2 6
4
2 6
1 2
1 3
4 6
1
2
3
2

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


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

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