Це інтерактивна задача.

Задано п'ятірку $(T,I,S_V,S_E,\iota)$, де:

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

Звичайна інформація має дві властивості: множину вершин і множину ребер. Нейтральний елемент має лише множину ребер, а недопустима інформація не має жодної з цих властивостей.

• Для інформації $o\in I\setminus\{\epsilon,\bot\}$ її множина вершин є двоелементною підмножиною $V$, позначається $S_V(o)$ та задовольняє $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\}$ її множина ребер є підмножиною $E$, позначається $S_E(o)$ та задовольняє $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$, відстань від яких до $u$ не перевищує $d$, а $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$ з індексом $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$ відповідно. Під час локального налагодження потрібно гарантувати, що для всіх $i\in[2,n]$ виконується $p_i<i$.
  • Наступні $q$ рядків містять по два цілі числа $u,d$, що описують один запит.

• Після зчитування бібліотека взаємодії виконує тестування. Якщо програма порушує обмеження бібліотеки, буде виведено відповідне повідомлення про помилку. Інакше скомпонований виконуваний файл виводить таке:

  • Один рядок із трьома цілими числами $C_1,C_2,C_3$, де:

    • $C_1$ — загальна кількість викликів функцій бібліотеки взаємодії у функції init.
    • $C_2$ — загальна кількість викликів функцій бібліотеки взаємодії протягом виконання програми.
    • $C_3$ — найбільша кількість викликів функцій бібліотеки взаємодії серед $q$ викликів ask.
    • У всіх трьох показниках враховуються лише виклики 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$.