P8262 [CTS2022] Long

This is an interactive problem. For local testing, you need `#include `. When submitting, please use the following template instead of including `long.h`. The method is to put this template directly into your code, and then complete the functions required by the problem. ```cpp struct sethash{ int val; void encode(); void decode(); void operator=(int x); }; struct infoset{ sethash sum; int sz; int size()const{ return sz; } }; extern const infoset emptyset; infoset merge(const infoset&a,const infoset&b); void report(infoset p); void init(int id,int n,int q,vectordad,vectorve); void modify(int x,int y); void ask(int x,int y); ``` *** The great scientist Xin plans to build the powerful AI Long to rule the world. After feeding it some Vietnamese competitive programming problems as a training set, she found that Long automatically generated a new problem and provided a solution. At the same time, Long also reduced $30\%$ of the inputs in the test set to this problem. Xin quickly copied down 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 is not that hard. Why can it solve $30\%$ of the problems in the test set?” Xin thought. Before closing the training results page, Xin suddenly noticed that, in the problem given by Long, the cost of merging information is not $O(1)$. Xin fell into deep thought and realized she could not solve this problem. To find out how hard it is, Xin presents it to you.

You need to maintain a rooted tree with root $1$. This tree has $n$ nodes. Initially, for all $2 \le i \le n$, node $i$ has a parent $p_i$, and it is guaranteed that $p_i \lt i$. At the beginning, you have $n$ sets $\{1\}, \{2\}, \cdots, \{n\}$. For any two sets $A$ and $B$, if $A \cap B = \empty$, then you can, in one operation, pay a cost of $|A| + |B|$ to obtain the set $A \cup B$. Then there are $q$ operations. Each operation is one of the following two types: - `0 a b`: Let $S$ be the set of nodes on the path from $a$ to $b$ in the tree. You need to represent $S$ as $\cup_{i=1}^{k} A_i$, where each $A_i$ is a set you have already obtained, and $\forall i \neq j, A_i \cap A_j = \empty$. The cost of answering one query using $(A_1, A_2, \cdots, A_k)$ is $k$. - `1 a b`: Change the parent of node $a$ to $b$. It is guaranteed that $a \gt 1$, and after the modification, these $n$ nodes still form a tree, but it is not guaranteed that $a \gt b$. In this operation, you may generate some new sets to handle future queries. Let the total cost consumed during the entire execution of your program be $C_1$, and the maximum cost consumed by a single operation be $C_2$. Each subtask will be scored in some way based on the values of $C_1$ and $C_2$.

### Implementation Details The header file defines a data type `infoset`, used to store the sets you have obtained. This type includes a member function `size()`, which indicates the size of the set. **The header file also provides a constant `emptyset` representing the empty set.** In addition, you can call the following functions: `infoset merge(const infoset&A,const infoset&B);` - Generate a new set $A \cup B$ at a certain cost. - Note that you may generate the same set multiple times, and the cost must be counted multiple times accordingly. `void report(infoset A);` - You may call this function only during a query operation, indicating that you need to pay a cost of $1$ to add a set $A$ into the final union. 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,vectordad,vectorve);` - You may preprocess some information before the $q$ operations start. - The cost consumed in this function will not be counted into the **maximum cost of a single operation**, but it will be counted into the **total cost during the entire execution**. - `id` indicates the subtask number, `n` indicates the total number of nodes, and `q` indicates the total number of operations. - The size of `dad` is $n-1$, and `dad[i]` indicates the parent of node $i+2$ at the initial moment. - The size of `ve` is $n$, and `ve[i]` indicates the initial set $\{i+1\}$. `void modify(int x,int y);` - Execute one modification operation, setting the parent of node $x$ to node $y$. `void ask(int x,int y);` - Execute one query operation, querying the tree-path information from $x$ to $y$. - You need to call `report` some number of times to answer the query. At the end of this query, the interaction library will check whether all sets $A$ you reported satisfy the conditions. During evaluation, the interaction library will call `init` exactly once, and then call `modify` and `ask` a total of $q$ times. This problem guarantees that the tree shape and the sequence of operations are fully determined before the interaction starts, and will not be constructed dynamically based on the interaction process with your program. Therefore, the interactive operations in this problem are deterministic, and you do not need to care about the specific implementation of these operations in the interaction library. During evaluation, the interaction library will use a special implementation: a single variable of type `infoset` will always consume $8$ bytes of memory. Please ensure that there are not too many variables of type `infoset` existing at the same time during the execution of your program. It is guaranteed that, under the call limits, the time required by the interaction library will not exceed $2\text{s}$; the memory consumed by the interaction library itself will not exceed $16\text{MB}$.

### Test Program Mode The `grader.cpp` in the provided files is a reference implementation of the interaction library. The interaction library used in the final testing is different from this reference implementation, so contestants’ solutions should not depend on the interaction library implementation. You need to compile to an executable program using the following command: `g++ grader.cpp long.cpp -o long -static -O2 -std=c++14` For the compiled executable: - The executable will read input data from standard input in the following format: - The first line contains an integer $id$, indicating the subtask number. - The second line contains two integers $n, q$, indicating the total number of nodes and the total number of operations. - The third line contains $n-1$ integers, indicating the parent node indices of nodes $2$ to $n$. - The next $q$ lines each contain three integers $op, x, y$, describing one operation. $op = 0$ means this is a query operation, and $op = 1$ means this is a modification operation. - After reading is completed, the interaction library will call the function `init` exactly once and then call `modify` or `ask` $q$ times, using the input data to test your functions. After the program runs normally, it will output several lines. Each line contains several numbers representing your answer 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 of a single operation, respectively. **The provided files include four sets of sample files, where the fourth set satisfies the special property of Subtask 2.** When testing samples, please ignore the comparison of the last line in the output file, because the last line output by the interaction library is the running cost of the program, not the query results of the query operations.

### Scoring **This problem is first subject to the same constraints as traditional problems.** For example, a compilation error will cause you to get $0$ points for the entire problem; runtime errors, exceeding the time limit, exceeding the memory limit, etc. will cause you to get $0$ points for the corresponding test points. You can only access the variables you define and those provided by the interaction library, as well as their corresponding memory space. Attempting to access other space may lead to compilation errors or runtime errors. On the basis of the above conditions, for a test point, if your program performs illegal function calls, fails to terminate normally, or provides an incorrect answer to a query operation, that test point will receive $0$ points. Otherwise, scoring will be based on the cost consumed by your program, with two scoring methods: - Scoring method 1: If $W_1 \gt 6 \cdot 10^8$, then the score for that test point is $0$. Otherwise, the score for that test point is $\frac{\frac{1.5 \cdot 10^8}{max(W_1, 1.5 \cdot 10^8)} \cdot 7 + 3}{10} \times$ the subtask score value of that test point. - Scoring method 2: If $W_2 \gt 2 \cdot 10^4$, then the score for that test point is $0$. Otherwise, the score for that test point is $\frac{5000}{max(W_2, 5000)} \times$ the subtask score value of that test point. Different subtasks use different scoring methods. The score of a subtask is the minimum of the scores of all test points in that subtask. ### Constraints and Agreements It is guaranteed that for all test points, $1 \le n, q \le 10^5$. | Subtask ID | $n, q \le$ | Special Property | Scoring Method | Score | | ---------- | ---------- | ---------------- | -------------- | ----- | | $1$ | $100$ | None | 1 | $10$ | | $2$ | $10^5$ | Yes | 1 | $20$ | | $3$ | $10^5$ | Yes | 2 | $20$ | | $4$ | $10^5$ | None | 1 | $30$ | | $5$ | $10^5$ | None | 2 | $20$ | Special property: It is guaranteed that at any time, except for node $1$, each node has at most one child. ### Afterword Xin found that you still did not solve this problem after five hours, and she was very satisfied with Long’s abilities. However, the next morning, Xin suddenly found that the complexity proof of Long’s solution was wrong. Translated by ChatGPT 5