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

Великая учёная 欣 собирается создать сильный искусственный интеллект 隆, чтобы править миром. После подачи нескольких вьетнамских задач по спортивному программированию в качестве обучающей выборки она обнаружила, что 隆 самостоятельно придумал новую задачу и предложил её решение. Кроме того, 隆 свёл к этой задаче 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, а затем суммарно $q$ раз вызовет modify и ask.

Гарантируется, что форма дерева и выполняемые операции полностью определены до начала взаимодействия и не создаются динамически в зависимости от взаимодействия с вашей программой. Поэтому интерактивные операции в этой задаче детерминированы; вам не нужно беспокоиться об их конкретной реализации в библиотеке взаимодействия.

При проверке библиотека взаимодействия использует специальную реализацию: одна переменная типа 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 и $q$ раз modify или ask, проверяя ваши функции на введённых данных. При нормальной работе программа выведет несколько строк, содержащих по несколько чисел, которые представляют ваши ответы на запросы. Последняя строка содержит два целых числа $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}$, умноженному на число баллов за подзадачу, к которой относится тест.
• Способ второй: если $W_2 \gt 2 \cdot 10^4$, за тест начисляется $0$ баллов; иначе балл за тест равен $\frac{5000}{max(W_2,5000)}$, умноженному на число баллов за подзадачу, к которой относится тест.

В разных подзадачах используются разные способы оценки. Балл за подзадачу равен минимуму баллов за все её тесты.

Ограничения

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

Специальное свойство: гарантируется, что в любой момент у каждой вершины, кроме вершины $1$, есть не более одного ребёнка.

Послесловие

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