| Автор: | Жюри ВКОШП-2011 | Автор задачи: Глеб Евстропов, Автор условия: Михаил Пядеркин | Ограничение времени: | 2 сек | |
| Входной файл: | tree.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | tree.out |
Глеб очень любит историю. Он приходит в полный восторг, когда ему предлагают изучить историю какой-либо конкретной династии. Глеб очень строго относится к чистоте крови, поэтому при анализе династии он включает в рассмотрение только мужчин, которые являются кровными потомками основателя династии по отцовской линии.
Один из главных методов исторического анализа династии — изучение количества сыновей некоторого ее представителя. Глеб же намеревается произвести настоящую революцию в исследованиях — он намерен изучать не просто количество сыновей, а количество внуков, правнуков, праправнуков и так далее. Однако, династии могли тянуться несколько десятков поколений, а значит общее число кровных потомков очень велико, так что Глебу стало очень тяжело работать. Поскольку на дворе сейчас XXI век, Глеб решил обратиться за помощью к квалифицированным программистам.
Династия представляет собой множество людей, один из которых называется основателем династии, а любой другой представитель династии U имеет отца V, являющегося представителем династии. При этом U является сыном V, или потомком U через 1 поколение. Потомком U через k + 1 поколение называется сын V некоторого потомка U через k поколений.
Глеба интересует информация о том, сколько у некоторого представителя династии V существует потомков через k поколений. Разумеется, Глеба интересует далеко не один такой вопрос.
В первом запросе тестового примера у представителя династии номер 1 есть два потомка во 2 поколении: 3 и 5.
В первой строке входного файла содержится одно число n — количество человек в династии, которую исследует Глеб (1 ≤ n ≤ 105), представители династии пронумерованы различными натуральными числами от 1 до n. Далее следуют n чисел, i-е из которых задает номер отца i-го представителя династии, или равно − 1, если соответствующий представитель является основателем династии.
Гарантируется, что основатель династии ровно один, и что любой упомянутый представитель династии является потомком основателя династии.
В следующей строке содержится число m — количество вопросов, которое интересует Глеба (1 ≤ m ≤ 105). Далее следует m строк, каждая из которых содержит два целых числа v и k (1 ≤ v ≤ n, 1 ≤ k ≤ 109) — номер исследуемого представителя династии и интересующее Глеба число поколений.
Для каждого вопроса выведите одно число — количество потомков через соответствующее число поколений у заданного представителя династии.
| № | Входной файл (tree.in) |
Выходной файл (tree.out) |
|---|---|---|
| 1 | |
|