题目描述

众所周知，在计算机科学中二进制可以表示世间万物，因此 THU 算协决定在世一大的校园网内种一些树以绿化环境。

不过，尽管服务器并不是土豆做的，但是由于更多的资源要用于和隔壁市一大竞争，所以校园网的空间有限。而以jpg格式，或者传统的存储树的方法种下一棵树的话，占用内存要以KB计，这是相当巨大的内存开销。但是，作为一位负责任的出题人，TA当然希望占用内存尽量少啦。

因此在经过反复磋商后， THU 算协决定采用最原始的二进制办法存储树。这样，游客们在看到这些二进制串的时候，只要按照规则在脑内把这些二进制串脑补成一棵棵生龙活虎的树就可以了。

这样一来问题就几乎解决了——唯一的问题是，这个规则似乎并不好设计。

具体来讲，THU 算协会给其一个成员 Alice 一棵有 $n$ 个点的有根树 $T$（其中 $n\le 70$）。她需要将这棵树转化为一个长度为 $128$ 的二进制串 $M$，并将 $n$ 和 $M$ 告知某位游客 Bob。而 Bob 需要在获得 $n$ 和 $M$ （这是 Bob 仅有的信息）后，恢复出一棵和 $T$ 同构的有根树。我们称两棵树同构当且仅当它们在节点无标号、考虑孩子顺序的意义下相同。

而你需要做的，就是为 Alice 和 Bob 分别实现编码函数和解码函数。

实现细节

你不需要，也不应该实现主函数，你只需要实现如下两个函数：

unsigned __int128 encoder(int n, const int *p);

void decoder(int n, unsigned __int128 M, int *p);

其中encoder函数为编码函数，该函数接受树的结点数$n$和描述一棵树的数组$p$，返回一个128位二进制串（以一个 unsigned __int128 的形式存储）。

decoder函数为解码函数，该函数接受树的结点数$n$和encoder函数返回的128位二进制串$M$，该函数可以修改数组$p$，使之代表一棵树。

其中，编码和解码函数都使用以下格式存储一棵树：树的结点按照 $1,2,\dots,n$ 编号，其中根节点是 $1$ 号结点；$p[i]$ 表示 $i$ 号结点的父亲，其中 $p[1] = 0$。

为了体现出孩子的顺序，规定孩子的顺序为按照结点编号从小到大排列。

注意：树的结点编号仅为传输的方便，在测试时，同构的树都被视为是相同的。

另外，你也可以根据自己的需要，定义其他变量或者函数。但你定义的全局变量在encoder阶段修改的值将不能应用于decoder阶段。

每一个测试点共包含$m$组数据，只有全部运行正确才能获得此测试点的分数。

**在多组数据的encoder之间，以及多组数据的decoder之间，你定义的全局变量的值可以共享。**你可以利用这一性质来合理编写你的程序。

你的encoder函数只能访问数组$p$的$1\thicksim n$位置且不能对其进行修改，decoder函数只能访问或修改数组$p$的$1\thicksim n$位置。

如何测试你的程序

本地已经下发了3个文件：grader.cpp、encoder.cpp和decoder.cpp。

你需要在本地将自己的程序命名为planttree.cpp，其中包含你编写的encoder和decoder两个函数。

将这4个程序放在同一个文件夹里，然后直接编译运行grader.cpp。

上述交互库按照以下格式输入数据：

• 第一行一个正整数 $m$，表示数据组数；
• 接下来连续输入 $m$ 组数据，对于每一组数据：
  • 第一行包含一个正整数 $n$，表示树的大小。
  • 第二行包含空格分开的 $n$ 个数 ，表示描述这棵树的$p$数组。

请务必确保输入数据格式符合上述要求，否则交互库可能出现意想不到的错误。

上述交互库会输出你的程序运行正确与否的相关信息。

注意：上述交互库运行过程中会创建并使用文件planttree.tmp。

输入格式

输出格式

样例 #1

样例输入 #1

1
4
0 1 1 1

样例输出 #1

提示

【样例解释 #1】

这一测试点只包含一棵四个节点的树，其中三个叶节点均以根节点作为父节点。

以下是一个并不保证正确，但能通过本例的编码和解码程序实现。你可以参照这一实现熟悉交互库的适用方法。

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;
}

【子任务】

本题设置 5 个子任务：

• 第 1 个子任务（20 分）的特殊限制：$n\leq 65$，$m\leq 3000$；
• 第 2 个子任务（15 分）的特殊限制：$m\leq 3000$；
• 第 3 个子任务（15 分）的特殊限制：树的深度不超过$10$，其中根节点($1$号结点)的深度为$1$；
• 第 4 个子任务（20 分）的特殊限制：树的每个结点最多有$2$个孩子；
• 第 5 个子任务（30 分）没有特殊限制。

对于所有测试点，保证 $n\leq 70$，$m\leq 10^5$。

【提示】

本题时间限制 2s，空间限制 512MB。保证对于任何合法的数据及在限制范围内的调用，交互库运行所用的时间不会超过 0.5s，运行所用的空间不会超过 64MB，也就是说，你实际可用的时间至少为 1.5s，实际可用的空间至少为 448MB。

交互库正常运行需包含的头文件已经给出，你的程序可以包含你需要的头文件。

注意交互库使用了 using namespace std;，你的程序需小心可能的变量名冲突问题。

为符合评测的实际情况，本题实际评测使用的交互库与下发的交互库不完全相同。

你的程序不能进行任何读入、输出和文件操作。

通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。

题目使用协议

来自 清华大学 2021 年全国优秀中学生信息学体验营 (THUSC 2021)。

以下『本仓库』皆指 THUSC 2021 官方仓库（https://gitlink.org.cn/thusaa/thusc2021）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址。
4. 清华大学计算机系保留一切权利。