P10243 [THUSC 2021] Planting Trees (Communication Problem, No Testdata Yet)

Since Luogu does not currently support judging communication problems, this problem currently has no testdata.

This is a **communication problem**. As everyone knows, in computer science, binary can represent everything in the world. Therefore, the THU Algorithm Association decided to plant some trees in the campus network of **Shi** No. 1 University to green the environment. However, although the servers are not made of potatoes, since more resources need to be used to compete with the neighboring **Shi** No. 1 University, the storage space of the campus network is limited. If you plant a tree using JPG format or traditional ways of storing trees, the memory usage is measured in KB, which is a huge overhead. But as a responsible problem setter, they of course hope the memory usage is as small as possible. So after repeated discussions, the THU Algorithm Association decided to use the most primitive binary method to store trees. In this way, when visitors see these binary strings, they only need to follow the rules and imagine these binary strings as vivid trees in their minds. Then the problem is almost solved—the only problem is that this rule does not seem easy to design. More specifically, the THU Algorithm Association will give one of its members, **Alice**, a rooted tree $T$ with $n$ nodes (where $n \le 70$). She needs to convert this tree into a binary string $M$ of length $128$, and tell $n$ and $M$ to a visitor **Bob**. After obtaining $n$ and $M$ (this is the only information **Bob** has), **Bob** needs to restore a rooted tree isomorphic to $T$. We say two trees are isomorphic if and only if they are the same in the sense that nodes are unlabeled and the order of children is considered. What you need to do is implement the encoding function and the decoding function for **Alice** and **Bob**, respectively. ### Implementation Details You do not need to, and should not, implement the main function. You only need to implement the following two functions: ```c++ unsigned __int128 encoder(int n, const int *p); void decoder(int n, unsigned __int128 M, int *p); ``` The `encoder` function is the encoding function. It takes the number of nodes $n$ and an array $p$ describing a tree, and returns a 128-bit binary string (stored as an `unsigned __int128`). The `decoder` function is the decoding function. It takes the number of nodes $n$ and the 128-bit binary string $M$ returned by the `encoder` function. It may modify the array $p$ so that it represents a tree. Both the encoding and decoding functions store a tree using the following format: the nodes are numbered $1, 2, \dots, n$, where the root is node $1$; $p[i]$ indicates the parent of node $i$, and $p[1] = 0$. To reflect the order of children, the order of children is defined as sorting by node number from small to large. Note: the node numbers are only for convenience of transmission. During testing, isomorphic trees are all considered the same. In addition, you may define other variables or functions as needed. **However, the values of global variables you modify during the `encoder` phase cannot be used in the `decoder` phase.** Each test point contains $m$ groups of data, and you can get the score for that test point only if all groups run correctly. **Between multiple data groups of `encoder`, and between multiple data groups of `decoder`, the values of global variables you define can be shared.** You can use this property to write your program properly. Your `encoder` function can only access positions $1 \thicksim n$ of array $p$ and must not modify it. Your `decoder` function can only access or modify positions $1 \thicksim n$ of array $p$. ### How to Test Your Program Three files have been provided locally: `grader.cpp`, `encoder.cpp`, and `decoder.cpp`. You need to name your program `planttree.cpp`, which contains the two functions `encoder` and `decoder` that you wrote. Put these four programs in the same folder, then compile and run `grader.cpp` directly. The interaction library reads input in the following format: - The first line contains a positive integer $m$, the number of data groups. - Then $m$ data groups follow. For each group: - The first line contains a positive integer $n$, the size of the tree. - The second line contains $n$ numbers separated by spaces, describing the array $p$ of this tree. Please make sure the input format strictly follows the requirements above; otherwise, the interaction library may produce unexpected errors. The interaction library will output information about whether your program runs correctly. Note: during execution, the interaction library will create and use a file named `planttree.tmp`.

N/A

N/A

**[Sample Explanation #1]** This test point contains only one tree with 4 nodes, where the three leaf nodes all take the root as their parent. Below is an implementation of encoding and decoding that is **not guaranteed to be correct**, but can pass this example. You may refer to it to get familiar with how to use the interaction library. ```c++ unsigned __int128 encoder(int n, const int *p) { return 0; } void decoder(int n, unsigned __int128 M, int *p) { p[1] = 0; p[2] = p[3] = p[4] = 1; } ``` **[Subtasks]** This problem has 5 subtasks: - Subtask 1 (20 points) has special constraints: $n \leq 65$, $m \leq 3000$. - Subtask 2 (15 points) has special constraints: $m \leq 3000$. - Subtask 3 (15 points) has special constraints: the tree depth does not exceed $10$, where the depth of the root (node $1$) is $1$. - Subtask 4 (20 points) has special constraints: each node has at most $2$ children. - Subtask 5 (30 points) has no special constraints. For all test points, it is guaranteed that $n \leq 70$, $m \leq 10^5$. **[Hints]** The time limit is 2 s and the memory limit is 512 MB. It is guaranteed that for any valid data and calls within the constraints, the time used by the interaction library will not exceed 0.5 s, and the memory used will not exceed 64 MB. That is, your actual available time is at least 1.5 s, and your actual available memory is at least 448 MB. The required header files for the interaction library have already been provided. Your program may include any header files you need. Note that the interaction library uses `using namespace std;`, so your program should be careful about possible variable name conflicts. To match the actual judging situation, the interaction library used in the actual evaluation is not exactly the same as the provided one. Your program must not perform any input, output, or file operations. Gaining points by accessing input/output files, attacking the judging system, or attacking the judging library is considered cheating, and the obtained score will be invalid. ### Problem Usage Agreement From the 2021 National Outstanding High School Students Informatics Experience Camp of Tsinghua University (THUSC 2021). The following “this repository” refers to the official THUSC 2021 repository ([https://gitlink.org.cn/thusaa/thusc2021](https://gitlink.org.cn/thusaa/thusc2021)) 1. Any organization or individual may use or repost the problems in this repository for free. 2. When using the problems in this repository, any organization or individual should do so free of charge and publicly. It is strictly forbidden to use these problems for profit or to add special access permissions to these problems. 3. If possible, when using the problems in this repository, please also provide the ways to obtain resources such as testdata, reference solutions, and editorials; otherwise, please attach the address of this repository. 4. The Department of Computer Science, Tsinghua University reserves all rights. Translated by ChatGPT 5