Background

This is an interactive problem.

The great scientist Xin is preparing to build a strong AI, Long, to rule the world. After inputting some Vietnamese algorithmic competition problems as a training set, she discovered that Long automatically generated a new problem and provided a solution. Long also reduced 30% of the input data in the test set to this problem. Xin hurriedly transcribed the problem as follows: Given a rooted tree, you need to support two operations:

• Query the sum of elements on a tree path.
• Change the parent of a node to another node.

"This problem isn't that strong; why can it solve 30% of the problems in the test set?" Xin wondered. Before closing the training results page, Xin suddenly realized that in the problem Long provided, the cost of merging information is not $O(1)$. Xin fell into deep thought and realized she couldn't solve this problem. To find out how difficult this problem is, Xin has placed it before you.

Description

You need to maintain a rooted tree with $1$ as the root. The tree has $n$ nodes. Initially, for all $2 \le i \le n$, node $i$ has a parent $p_i$, guaranteed to satisfy $p_i < i$.

At the beginning, you have $n$ sets $\{1\}, \{2\}, \dots, \{n\}$. For any two sets $A$ and $B$, if $A \cap B = \varnothing$, you can perform an operation to obtain the set $A \cup B$ at the cost of $|A| + |B|$.

Afterward, there are $q$ operations. Each operation is of one of two types:

• 0 a b: Let $S$ be the set of nodes on the path between $a$ and $b$ in the tree. You need to represent $S$ as $\cup_{i=1}^{k} A_i$, where $A_i$ are sets you have already obtained, and $\forall i \neq j, A_i \cap A_j = \varnothing$. The cost of answering a query with $(A_1, A_2, \dots, A_k)$ is $k$.
• 1 a b: Change the parent of node $a$ to $b$. It is guaranteed that $a > 1$ and that the $n$ nodes still form a tree after the modification, but it is not guaranteed that $a > b$. You may generate new sets during this operation to handle future queries.

Let $C_1$ be the total cost consumed during the entire execution of your program, and $C_2$ be the maximum cost consumed by a single operation. Each subtask will be scored based on $C_1$ and $C_2$ in a specific way.

Implementation Details

Please ensure your program begins with #include "long.h".

The header file defines the data type infoset, used to store the sets you have obtained.

This type includes a member function size(), which returns the size of the set. The header file also provides the constant emptyset representing the empty set.

Additionally, you can call the following functions:

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

• Generates a new set $A \cup B$ at a certain cost.
• Note that you can generate the same set multiple times, and the cost will be counted each time.

void report(infoset A);

• You can only call this function during a query operation, indicating that you want to add a set $A$ to the final union at a cost of $1$.

You do not need to, and should not, implement the main function. You need to implement the following functions:

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

• You can preprocess information before the $q$ operations begin.
• The cost consumed in this function will not be counted towards the maximum cost of a single operation, but it will be counted towards the total cost consumed during the entire program execution.
• id is the subtask number, n is the total number of nodes, and q is the total number of operations.
• dad has a size of $n-1$, where dad[i] is the parent of node $i+2$ at the initial moment.
• ve has a size of $n$, where ve[i] is the initial set $\{i+1\}$.

void modify(int x, int y);

• Perform a modification operation to set the parent of node $x$ to node $y$.

void ask(int x, int y);

• Perform a query operation to query the information on the tree path from $x$ to $y$.
• You need to call report several times to answer the query. At the end of the query, the interactive library will check whether all the sets $A$ you reported satisfy the conditions.

During evaluation, the interactive library will call init exactly once, followed by a total of $q$ calls to modify or ask.

This problem guarantees that the tree structure and the operations are fully determined before the interaction begins; they are not constructed dynamically based on your program's responses. Therefore, all interactive operations are deterministic, and you do not need to worry about their specific implementation within the interactive library.

During evaluation, the interactive library uses a special implementation. A single infoset variable will constantly consume 8 bytes of memory. Please ensure that there are not too many infoset variables existing simultaneously during your program's execution.

It is guaranteed that the time required for the interactive library to run within the call limits does not exceed 2s, and the memory consumed by the interactive library itself does not exceed 16MB.

Testing Your Program

The grader.cpp provided in the download is a reference implementation of the interactive library. The interactive library used during final testing differs from this reference implementation, so your solution should not rely on the specific implementation of the interactive library.

You should use the following command to compile your program: g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

For the compiled executable:

• The executable will read data from standard input in the following format:
  • The first line contains an integer $id$, representing the subtask number.
  • The second line contains two integers $n, q$, representing the total number of nodes and operations.
  • The third line contains $n-1$ integers, representing the parent node IDs of nodes $2$ through $n$.
  • The next $q$ lines each contain three integers $op, x, y$, describing an operation. $op=0$ indicates a query operation, and $op=1$ indicates a modification operation.
• After reading, the interactive library will call init exactly once and modify or ask $q$ times to test your functions using the input data. After the program runs normally, it will output several lines, each containing several numbers representing your answers to each query operation. The last line will include two integers $W_1, W_2$, representing the total cost consumed by your program and the maximum cost consumed by a single operation, respectively.

The download includes four sets of sample files, where the fourth set satisfies the special properties of subtask 2. Please ignore the comparison of the last line of the output when testing samples, as the last line output by the interactive library represents the program's running cost rather than the query results.

Scoring

This problem is subject to the same constraints as traditional problems. For example, compilation errors will result in 0 points for the entire problem, while runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test cases. You may only access variables you have defined and those provided by the interactive library and their corresponding memory space; attempting to access other memory may lead to compilation or runtime errors.

Under the above conditions, if the program performs illegal function calls, does not terminate normally, or provides incorrect answers to query operations in a test case, that test case will receive 0 points. Otherwise, it will be scored based on the cost consumed by your program using one of two methods:

• Method 1: If $W_1 > 6 \cdot 10^8$, the test case receives 0 points; otherwise, the score is $\frac{\frac{1.5 \cdot 10^8}{\max(W_1, 1.5 \cdot 10^8)} \cdot 7 + 3}{10} \times \text{Subtask Score}$.
• Method 2: If $W_2 > 2 \cdot 10^4$, the test case receives 0 points; otherwise, the score is $\frac{5000}{\max(W_2, 5000)} \times \text{Subtask Score}$.

Different subtasks use different scoring methods. The score for a subtask is the minimum score among all test cases in that subtask.

Constraints

It is guaranteed that for all test cases, $1 \le n, q \le 10^5$.

Special Property: It is guaranteed that at any time, every node except node $1$ has at most one child.

Time Limit: $10s$

Memory Limit: $1024MB$

Note

Xin discovered that you still hadn't solved the problem after five hours, and she was very satisfied with Long's capabilities. However, the next morning, Xin suddenly realized that the proof of the complexity of Long's approach was wrong.