Передісторія

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

Видатна науковиця 欣 збирається створити сильний штучний інтелект 隆, щоб панувати над світом. Після введення кількох в'єтнамських задач з алгоритмічних змагань як навчальної вибірки вона виявила, що 隆 автоматично сформулював нову задачу та надав її розв'язання. Водночас 隆 звів до цієї задачі 30% вхідних даних тестової вибірки. 欣 поспішила записати цю задачу: Дано кореневе дерево, потрібно підтримувати два види операцій.

• Знайти суму елементів на шляху в дереві.
• Змінити батька однієї вершини на іншу вершину.

«Ця задача не така вже й потужна. Чому вона дозволяє розв'язати 30% задач тестової вибірки?» — подумала 欣. Перш ніж закрити сторінку результатів навчання, 欣 раптом помітила, що в задачі, запропонованій 隆, вартість об'єднання інформації не дорівнює $O(1)$. 欣 замислилася й зрозуміла, що не вміє розв'язувати цю задачу. Щоб дізнатися, наскільки вона складна, 欣 запропонувала цю задачу вам.

Умова задачі

Вам потрібно підтримувати кореневе дерево з коренем у вершині $1$. У дереві $n$ вершин. Спочатку для всіх $2 \le i \le n$ вершина $i$ має батька $p_i$; гарантовано, що $p_i \lt i$.

Спочатку у вас є $n$ множин $\{1\},\{2\},\cdots,\{n\} $. Для будь-яких двох множин $A$ і $B$, якщо $A \cap B=\varnothing$, ви можете за одну операцію з вартістю $|A|+|B|$ отримати множину $A \cup B$.

Далі відбудеться $q$ операцій. Кожна операція належить до одного з двох типів.

• 0 a b Позначимо через $S$ множину вершин на шляху між $a$ і $b$ у дереві. Потрібно подати $S$ як $\cup_{i=1}^{k}A_i$, де $A_i$ — множини, які ви вже отримали, і $\forall i \neq j,A_i \cap A_j=\varnothing$. Вартість відповіді на один запит за допомогою $(A_1,A_2,\cdots,A_k) $ дорівнює $k$.
• 1 a b Змінити батька вершини $a$ на $b$. Гарантовано, що $a \gt 1$ і після зміни ці $n$ вершин усе ще утворюють дерево, але не гарантовано, що $a \gt b$. Під час цієї операції ви можете створювати нові множини для відповідей на подальші запити.

Позначимо загальну вартість за весь час роботи вашої програми через $C_1$, а найбільшу вартість окремої операції — через $C_2$. Бали за кожну підзадачу нараховуються певним способом залежно від величин $C_1,C_2$.

Деталі реалізації

Переконайтеся, що на початку вашої програми є #include "long.h".

У заголовковому файлі визначено тип даних infoset для зберігання отриманих вами множин.

Цей тип має метод size(), що повертає розмір множини. Заголовковий файл також надає константу emptyset, яка позначає порожню множину.

Крім того, ви можете викликати такі функції:

infoset merge(const infoset&A,const infoset&B);

• Створює нову множину $A \cup B$ з певною вартістю.
• Зауважте, що одну й ту саму множину можна створювати повторно багато разів, і вартість враховується щоразу.

void report(infoset A);

• Цю функцію можна викликати лише під час операції запиту. Вона означає, що ви додаєте множину $A$ до остаточного об'єднання з вартістю $1$.

Вам не потрібно й не слід реалізовувати головну функцію. Потрібно реалізувати такі функції:

void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);

• Ви можете попередньо обробити деяку інформацію до початку $q$ операцій.
• Вартість, витрачена в цій функції, не враховується в найбільшій вартості окремої операції, але враховується в загальній вартості за весь час роботи програми.
• id — номер підзадачі, n — загальна кількість вершин, q — загальна кількість операцій.
• Розмір dad дорівнює $n-1$, а dad[i] — батько вершини $i+2$ у початковий момент.
• Розмір ve дорівнює $n$, а ve[i] — початкова множина $\{i+1\}$.

void modify(int x,int y);

• Виконує операцію зміни: встановлює вершину $y$ батьком вершини $x$.

void ask(int x,int y);

• Виконує операцію запиту інформації про шлях від $x$ до $y$ у дереві.
• Для відповіді на запит потрібно викликати report кілька разів. Наприкінці цього запиту інтерактивна бібліотека перевірить, чи всі повідомлені вами множини $A$ задовольняють умови.

Під час перевірки інтерактивна бібліотека спочатку один раз викличе init, а потім викличе modify та ask загалом $q$ разів.

Гарантовано, що форма дерева й виконувані операції повністю визначені до початку взаємодії та не будуються динамічно залежно від взаємодії з вашою програмою. Отже, інтерактивні операції в цій задачі детерміновані, і вам не потрібно зважати на конкретну реалізацію цих операцій в інтерактивній бібліотеці.

Під час перевірки інтерактивна бібліотека використовуватиме спеціальну реалізацію, за якої одна змінна типу infoset завжди займає $8$ байтів пам'яті. Переконайтеся, що під час роботи вашої програми одночасно не існує надто багато змінних типу infoset.

Гарантовано, що за дотримання обмеження на кількість викликів час роботи інтерактивної бібліотеки не перевищує 2 с; сама інтерактивна бібліотека використовує не більше 16 МБ пам'яті.

Тестування програми

Файл grader.cpp у наданих матеріалах містить еталонну реалізацію інтерактивної бібліотеки. Реалізація, що використовуватиметься під час остаточної перевірки, відрізняється від неї, тому розв'язок учасника не повинен залежати від реалізації інтерактивної бібліотеки.

Щоб отримати виконуваний файл, потрібно скомпілювати програму такою командою: g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

Для отриманого виконуваного файлу:

• Виконуваний файл читає зі стандартного вводу дані в такому форматі:

  • Перший рядок містить ціле число $id$ — номер підзадачі.
  • Другий рядок містить два цілі числа $n,q$ — загальну кількість вершин і загальну кількість операцій.
  • Третій рядок містить $n-1$ цілих чисел — номери батьків вершин від $2$ до $n$ відповідно.
  • Наступні $q$ рядків містять по три цілі числа $op,x,y$, що описують операцію. $op=0$ означає запит, а $op=1$ — зміну.
• Після читання даних інтерактивна бібліотека викличе функцію init рівно один раз, а modify або ask — $q$ разів, щоб перевірити ваші функції на вхідних даних. Після нормальної роботи програма виведе кілька рядків, кожен з кількома числами, що представляють вашу відповідь на відповідний запит; останній рядок міститиме два цілі числа $W_1,W_2$ — загальну вартість роботи програми та найбільшу вартість окремої операції відповідно.

Надані матеріали містять чотири набори файлів прикладів, причому четвертий приклад задовольняє особливу властивість другої підзадачі. Під час перевірки прикладів ігноруйте порівняння останнього рядка вихідного файлу, оскільки останній рядок, виведений інтерактивною бібліотекою, містить вартість роботи програми, а не відповідь на запит.

Оцінювання

Передусім на цю задачу поширюються ті самі обмеження, що й на звичайні задачі. Наприклад, помилка компіляції дає $0$ балів за всю задачу, а помилка виконання, перевищення обмеження часу, перевищення обмеження пам'яті тощо дають $0$ балів за відповідний тест. Ви можете звертатися лише до змінних, визначених вами та інтерактивною бібліотекою, і до відповідних областей пам'яті. Спроба доступу до інших областей може спричинити помилку компіляції або виконання.

За дотримання наведених вище умов, якщо на тесті програма виконує недопустимий виклик функції, не завершується нормально або дає неправильну відповідь на запит, за цей тест нараховується $0$ балів. Інакше залежно від вартості роботи вашої програми застосовується один із двох способів оцінювання:

• Спосіб оцінювання один: якщо $W_1 \gt 6 \cdot 10^8$, тест дає $0$ балів; інакше бал за тест дорівнює $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10} \times \text{бал підзадачі, до якої належить цей тест}$.
• Спосіб оцінювання два: якщо $W_2 \gt 2 \cdot 10^4$, тест дає $0$ балів; інакше бал за тест дорівнює $\frac{5000}{max(W_2,5000)} \times \text{бал підзадачі, до якої належить цей тест}$.

Різні підзадачі використовують різні способи оцінювання. Бал за підзадачу дорівнює найменшому балу серед усіх її тестів.

Обмеження

Гарантовано, що в усіх тестах $1 \le n,q \le 10^5$.

Особлива властивість: гарантовано, що в кожен момент кожна вершина, крім вершини $1$, має щонайбільше одного сина.

Післямова

Побачивши, що ви не розв'язали задачу навіть за п'ять годин, 欣 була дуже задоволена здібностями 隆. Проте наступного ранку 欣 раптом виявила, що доведення складності алгоритму 隆 було неправильним.