题目类型说明

这是一道提交函数题。

你需要提交一个源文件，在其中实现评测程序要求的两个函数：

std::vector<std::pair<int, int>> encode(int n, std::vector<bool> data);
std::vector<bool> decode(int n, std::vector<std::pair<int, int>> tree);

不要编写 main 函数，不要读写标准输入输出。你的代码会与系统提供的 grader.cpp 一起编译。

提交文件开头需要包含：

#include "bits_and_tree.h"

题目描述

给定一个长度为 2N 的二进制串 S，你需要用一棵有 N 个点的无标号无向树来编码它的尽可能长的前缀。

你需要实现两个函数：

• encode：接收原始二进制串，并构造一棵有 N 个点的树；
• decode：接收一棵被破坏后的树，并恢复尽可能长的正确前缀。

通信过程如下：

1. 你先用 encode 把原串编码成一棵有 N 个点、N-1 条边的树；
2. 系统会对这棵树做一次破坏：新增一个额外节点，并把它连接到原树中的某个节点上；
3. 得到的新树有 N+1 个点、N 条边；
4. 然后系统会把这棵树的节点重新随机编号，并随机打乱边顺序，以及随机交换每条边两个端点的顺序；
5. 你收到这棵被破坏后的树，调用 decode 还原一个比特串。

你的目标是：无论额外节点连到原树哪个位置，decode 返回的比特串都要与原串 S 拥有尽可能长的公共前缀。

函数说明

encode

std::vector<std::pair<int, int>> encode(int n, std::vector<bool> data);

• n：允许使用的节点数，即 N；
• data：原始二进制串。

你需要返回恰好 N-1 条边，表示一棵由 0..N-1 编号的无向树。

decode

std::vector<bool> decode(int n, std::vector<std::pair<int, int>> tree);

• n：原始的 N；
• tree：被破坏后的树，它有 N 条边、N+1 个点。

你需要返回一个比特序列，使它尽可能与原始 data 的前缀一致。

数据范围

• T = 2
• N = 200
• data 的长度为 2N

评分规则

如果 encode 构造出的图不是合法树，则该测试点得分为 0。

否则，设你在该测试点下能保证恢复出的最短正确前缀长度为 x，则该测试点得分由下表的分段线性函数给出：

也就是连接以下折点所形成的分段线性函数：

(1, 5), (5, 10), (10, 20), (85, 45), (100, 55), (170, 75), (205, 100)

Hydro 配置中，所有正式测试点放在同一个 min 子任务里，因此最终得分等价于对所有测试点取最差表现后再套用上面的评分曲线。

本地测试（Hydro 配置包）

Hydro 版 grader.cpp 读取格式为：

• 第一行：T seed
• 接下来 T 组：
  • 一行一个整数 N
  • 一行一个长度为 2N 的 01 串

grader.cpp 会：

1. 调用一次 encode；
2. 枚举额外节点连接到原树中每个点的位置；
3. 随机重标号、随机打乱边顺序、随机翻转边端点；
4. 调用 decode；
5. 输出该测试点下的最短正确前缀长度。