Məsələlər
Братья по крови наносят ответный удар
Братья по крови наносят ответный удар
Поликарп раздобыл дерево родственных связей. Найденное дерево описывает родственные связи \textbf{n} человек, пронумерованных от \textbf{1} до \textbf{n}. Каждый человек в этом дереве имеет не более одного непосредственного предка. Также каждый человек в дереве имеет коня некоторого типа, человек номер \textbf{x} имеет коня типа \textbf{t_x}. Типы коней не обязательно уникальные.
Назовем человека с номером \textbf{a} \textbf{1}-предком человека с номером \textbf{b}, если человек с номером \textbf{a} является непосредственным предком человека с номером \textbf{b}.
Назовем человека с номером a \textbf{k}-предком (\textbf{k} > \textbf{1}) человека с номером \textbf{b}, если у человека с номером \textbf{b} есть \textbf{1}-предок, и человек с номером \textbf{a} является \textbf{(k-1)}-предком \textbf{1}-предка человека с номером \textbf{b}.
В найденном дереве родственные связи не образуют циклов. Другими словами не существует человека, который непосредственно или косвенно является собственным предком (то есть является \textbf{x}-предком самого себя, для некоторого \textbf{x}, \textbf{x} > \textbf{0}).
Назовем человека с номером \textbf{a} \textbf{k}-сыном человека с номером \textbf{b}, если человек с номером \textbf{b} является \textbf{k}-предком человека с номером \textbf{a}.
Поликарп очень сильно интересуется сколько у кого и каких коней. Он записал на листочке \textbf{m} пар чисел \textbf{v_i}, \textbf{k_i}. Помогите ему для каждой пары \textbf{v_i}, \textbf{k_i} узнать величину \textit{конности} множества \textbf{k_i}-сыновей человека с номером \textbf{v_i}.
\textit{Конностью} множества людей \textbf{p_1}, \textbf{p_2}, ..., \textbf{p_r} (\textbf{p_1} < \textbf{p_2} < ... < \textbf{p_r}) называется число (\textbf{p_1} → (\textbf{p_2} → (... → \textbf{p_r}))). \textit{Конность} пустого множества равно нулю. Здесь операция \textbf{x} → \textbf{y} обозначает операцию побитового \textbf{СЛЕДОВАТЕЛЬНО} двух \textbf{30}-битных чисел. Подробное описание операции смотрите в примечании.
\InputFile
В первой строке входных данных записано единственное целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^5}) --- количество людей в дереве. В следующих \textbf{n} строках записано описание людей в дереве. В \textbf{i}-той из этих строк записаны через пробел целое число \textbf{t_i} и целое число \textbf{r_i} (\textbf{0} ≤ \textbf{t_i} ≤ \textbf{10^9}, \textbf{0} ≤ \textbf{r_i} ≤ \textbf{n}), где \textbf{t_i} --- тип коня человека с номером \textbf{i}, а \textbf{r_i} --- номер непосредственного предка человека с номером \textbf{i} или \textbf{0} если у человека с номером \textbf{i} нет непосредственного предка.
В следующей строке записано единственное целое число \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{10^5}) --- количество записей Поликарпа. В \textbf{m} следующих строках записаны пары целых чисел через пробел. В \textbf{i}-ой строке записаны целые числа \textbf{v_i}, \textbf{k_i} (\textbf{1 }≤ \textbf{v_i}, \textbf{k_i} ≤ \textbf{n}).
Гарантируется, что родственные связи не образуют циклов.
\OutputFile
Выведите \textbf{m} целых чисел, разделенных пробельными символами, --- ответы на записи Поликарпа. Ответы для записей выводите в том порядке, в котором записи встречаются во входных данных.
\Note
Результат операции побитового \textbf{СЛЕДОВАТЕЛЬНО} двух \textbf{30}-битных чисел --- это \textbf{30}-битное число, каждый из \textbf{30 }бит которого получается операцией битового СЛЕДОВАТЕЛЬНО двух битов операндов. В частности
\textbf{10 }→\textbf{ 32 = 1073741813}.
Таблица истинности для операции СЛЕДОВАТЕЛЬНО для битов:
\begin{itemize}
\item \textbf{0} → \textbf{0 = 1};
\item \textbf{0} → \textbf{1 = 1};
\item \textbf{1} → \textbf{0 = 0};
\item \textbf{1} → \textbf{1 = 1}.
\end{itemize}
Giriş verilənləri #1
6 1 0 1 1 0 1 3 2 4 2 5 2 4 1 1 1 2 2 1 3 1
Çıxış verilənləri #1
1073741822 1073741823 1073741823 0