Локдаун Империи
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 6
3 4
3 5
4 6
1 6
2 6
4
2 6
1 2
1 3
4 6 | 1
2
3
2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
