Это интерактивная задача.

Дана пятёрка $(T,I,S_V,S_E,\iota)$, где:

• $T$ — корневое дерево $T=(V,E)$ с $n$ вершинами; $V$ — множество его вершин, $E$ — множество рёбер. Вершины пронумерованы $1,2,\ldots,n$, корень имеет номер $1$.
• $I$ — множество, элементы которого называются информацией. В нём есть два различных особых элемента: нейтральный элемент $\epsilon$ и недопустимая информация $\bot$.

Обычная информация имеет два атрибута: множество вершин и множество рёбер. У нейтрального элемента есть только множество рёбер, а у недопустимой информации нет ни одного из этих атрибутов.

• Для информации $o\in I\setminus\{\epsilon,\bot\}$ множество вершин $S_V(o)$ является двухэлементным подмножеством $V$: $S_V(o)\subseteq V$ и $|S_V(o)|=2$. Разность двух множеств $A,B$ определяется как $A\setminus B=\{x\in A\mid x\notin B\}$.
• Для информации $o\in I\setminus\{\bot\}$ множество рёбер $S_E(o)$ является подмножеством $E$: $S_E(o)\subseteq E$. Множество рёбер нейтрального элемента пусто: $S_E(\epsilon)=\varnothing$.
• Для любого ребра $e\in E$, $e=(u,v)$, существует информация $\iota(e)\in I$, множество вершин которой состоит из концов ребра, а множество рёбер — из самого ребра: $S_V(\iota(e))=\{u,v\}$, $S_E(\iota(e))=\{e\}$.

Информацию можно объединять двумя способами, обозначаемыми $R$ и $C$. Для любых $a,b\in I$ обозначим $r=R(a,b)$, $c=C(a,b)$, где $r,c\in I$. Выполняются условия:

• Объединение нейтрального элемента с любой информацией даёт эту информацию. Если $a=\epsilon$, то $r=c=b$; если $b=\epsilon$, то $r=c=a$.
• Объединение недопустимой информации с любой информацией даёт недопустимую информацию. Если $a=\bot$ или $b=\bot$, то $r=c=\bot$.
• В остальных случаях, если пересечение множеств рёбер непусто или размер пересечения множеств вершин не равен $1$, результат объединения недопустим. То есть, если $S_E(a)\cap S_E(b)\ne\varnothing$ или $|S_V(a)\cap S_V(b)|\ne1$, то $r=c=\bot$.
• Иначе

$$ S_E(r)=S_E(c)=S_E(a)\cup S_E(b), $$

$$ S_V(r)=S_V(a), $$

$$ S_V(c)=S_V(a)\oplus S_V(b). $$

Здесь $\oplus$ — симметрическая разность множеств: $A\oplus B=(A\cup B)\setminus(A\cap B)$.

Расстояние между двумя вершинами дерева $T$ — количество рёбер единственного простого пути между ними.

Даны параметр оценки $M$ и $q$ запросов. Каждый запрос задаёт вершину дерева $u$ и неотрицательное целое число $d$. Пусть $X$ — множество всех вершин $T$ на расстоянии не более $d$ от $u$, а $Y=\{(a,b)\in E\mid a,b\in X\}$ — множество внутренних рёбер $X$. Можно доказать, что из $\epsilon$ и всех $\iota(e)$ ($e\in E$) всегда можно за конечное количество вызовов $R,C$ получить информацию $o\ne\bot$ с $S_E(o)=Y$.

Для каждого запроса постройте такую информацию $o$, используя суммарно не более $M$ вызовов $R$ и $C$. В частности, при $d=0$ можно просто вернуть нейтральный элемент $\epsilon$.

Детали реализации

Убедитесь, что в начале программы присутствует #include "count.h".

В заголовке count.h реализовано следующее:

1. Определён тип данных info, соответствующий информации.
2. Определена константа emptyinfo типа info, соответствующая $\epsilon$. Её можно использовать непосредственно.
3. Определены и реализованы две функции объединения информации, которые можно вызывать непосредственно:

info MR(info a,info b);
info MC(info a,info b);

• Эти функции возвращают информацию, соответствующую $R(a,b)$ и $C(a,b)$.

Вы должны гарантировать, что результат вызова $R(a,b)$ или $C(a,b)$ не равен $\bot$, иначе программа может вести себя некорректно.

1. Определена и реализована функция проверки, является ли информация нейтральным элементом. Её можно вызывать непосредственно:

bool isempty(info a);

• Эта функция возвращает истину тогда и только тогда, когда $a$ — нейтральный элемент.

Более подробные сведения о реализации можно найти в предоставленной библиотеке взаимодействия.

Не нужно и не следует реализовывать главную функцию. Реализуйте следующие функции:

void init(int T, int n, int q, vector<int> fa, vector<info> e, int
   M);

• $T$ — номер теста, $n$ — количество вершин дерева, $q$ — количество запросов, $M$ — параметр оценки данного теста.
• Длина fa и e равна $n-1$. Для $0\le i<n-1$ значения $fa[i]$ и $i+2$ являются концами ребра $e_i$, а e[i] — элемент типа info, соответствующий $\iota(e_i)$ из условия. Гарантируется $fa[i]<i+2$.

info ask(int u, int d);

• Задаётся запрос; смысл параметров описан в условии. Функция должна вернуть информацию, удовлетворяющую требованиям задачи.

При окончательной проверке в каждом тесте библиотека взаимодействия вызовет init ровно один раз, затем $q$ раз вызовет ask. В ней используется особая реализация: одна переменная типа info всегда занимает 12 байт памяти. Это отличается от предоставленной библиотеки. Чтобы уложиться в ограничение памяти во время выполнения, не допускайте одновременного существования слишком большого количества переменных типа info.

Гарантируется, что при соблюдении ограничений на количество вызовов и отсутствии вызовов isempty окончательная библиотека взаимодействия использует не более 0,6 секунды и 16 MiB памяти. Если выполняются только $10^8$ вызовов isempty, время работы окончательной библиотеки не превышает 0,25 секунды.

В выданных файлах есть пример программы count.cpp, на основе которого можно написать решение. Также предоставлен резервный файл count_backup.h, гарантированно полностью совпадающий с count.h.

Проверка программы

В каталоге задачи предоставлены две эталонные реализации библиотеки взаимодействия — grader.o и checker.o, объектные файлы для компоновки, полученные из двух разных библиотек. Реализация на окончательной проверке отличается от них, поэтому решение не должно зависеть от конкретной реализации библиотеки взаимодействия или типа info в count.h.

Для компоновки нужно изменить выданный файл count.h. При компоновке исходного файла count.cpp с grader.o закомментируйте строку 5 в count.h и оставьте строку 4. Для checker.o, наоборот, закомментируйте строку 4 и оставьте строку 5. Можно самостоятельно изменять реализацию count.h для компиляции разных программ.

После изменений можно скомпилировать исполняемую программу в каталоге задачи командами:

g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o grader.o -o count
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o checker.o -o count

Первая команда компилирует текущий count.cpp и компонует его с grader.o, создавая исполняемый файл count. Вторая команда компилирует текущий count.cpp и компонует его с checker.o, также создавая count.

Полученный указанным способом исполняемый файл count работает следующим образом.

Он считывает со стандартного ввода данные следующего формата:

• Первая строка содержит четыре целых числа $id,n,q,M$ — номер теста, количество вершин дерева, количество запросов и параметр оценки.
• Вторая строка содержит $n-1$ целых чисел $p_2,p_3,\ldots,p_n$ — номера родителей вершин от $2$ до $n$. При локальной отладке нужно гарантировать $p_i<i$ для всех $i\in[2,n]$.
• Следующие $q$ строк содержат по два целых числа $u,d$, описывающих запрос.

После чтения библиотека взаимодействия выполняет проверку. Если программа нарушает её ограничения, в выводе появится соответствующее сообщение об ошибке. В противном случае скомпонованный исполняемый файл выводит:

• Одну строку с тремя целыми числами $C_1,C_2,C_3$, где:
• $C_1$ — общее количество вызовов функций библиотеки взаимодействия в init.
• $C_2$ — общее количество вызовов функций библиотеки взаимодействия за всё время работы программы.
• $C_3$ — максимальное количество вызовов функций библиотеки взаимодействия за один вызов ask среди всех $q$ запросов.
• В этих трёх величинах учитываются только вызовы MR и MC, а вызовы isempty не учитываются.

Возможности проверки зависят от выбранного объектного файла:

• grader.o не проверяет правильность информации, возвращаемой ask, но помогает проверить допустимость взаимодействия. Его время работы наиболее близко к окончательной библиотеке, поэтому его можно использовать для проверки скорости, но он не гарантирует правильность программы.
• checker.o проверяет правильность информации, возвращаемой ask, а также допустимость взаимодействия. Кроме того, он проверяет правильность информации, возвращаемой ask. Эта программа позволяет проверить правильность ответов.

При отладке данные, подаваемые исполняемому файлу count, должны соответствовать описанному формату, иначе правильность вывода не гарантируется.

Примеры

Пример 1

См. файлы count/count1.in и count/count1.ans в каталоге участника.

Пример 2

См. файлы count/count2.in и count/count2.ans в каталоге участника.

Этот пример удовлетворяет особому свойству A из ограничений.

Пример 3

См. файлы count/count3.in и count/count3.ans в каталоге участника.

Этот пример удовлетворяет особому свойству B из ограничений.

Пример 4

См. файлы count/count4.in и count/count4.ans в каталоге участника.

Подзадачи

При окончательной проверке принимается только count.cpp; изменение других файлов в каталоге участника на результат не влияет. Обратите внимание:

• Не гарантируется, что неинициализированная переменная типа info равна emptyinfo.
• Не пытайтесь читать или изменять поля типа info: это считается атакой на библиотеку взаимодействия.
• Не вызывайте MR и MC до вызова init, иначе возможно неопределённое поведение.
• Разрешается обращаться только к определённым вами переменным и переменным типа info, возвращённым библиотекой. Попытка обращения к другой памяти может привести к ошибке компиляции или выполнения.

Сначала применяются обычные ограничения традиционных задач: например, ошибка компиляции даёт 0 баллов за всю задачу, а ошибка выполнения, превышение времени или памяти — 0 баллов за соответствующий тест.

Кроме того, если в тесте программа выполняет недопустимый вызов функции или даёт неверный ответ на запрос, за тест начисляется 0 баллов. Иначе пусть $C_1$ — количество вызовов функций библиотеки в init, а $C_3$ — максимальное количество таких вызовов среди всех $q$ вызовов ask. Если $C_1\le3\cdot10^7$ и $C_3$ не превышает параметр оценки $M$ данного теста, вы получаете баллы за этот тест; иначе баллы не начисляются. При вычислении $C_1,C_3$ учитываются только вызовы MR, MC, но не isempty.

Ограничения

Для всех тестов $1\le n\le2\cdot10^5$, $1\le q\le10^6$. В каждом запросе $1\le u\le n$, $1\le d\le n-1$.

Особое свойство A: для любого $i\in[1,n-1]$ родителем вершины $i+1$ является $i$.

Особое свойство B: во всех запросах $u=1$.

Особое свойство C: во всех запросах $d\le100$.

Особое свойство D: во всех запросах $d\ge1000$.