P14392 [JOISC 2017] 都市 / City【通信题暂无法评测】
题目描述
JOI 王国内有许多城市。道路网络满足以下条件：
- （条件 1）城市编号从 $0$ 到 $N - 1$。其中，$N$ 是 JOI 王国内的城市总数。
- （条件 2）城市之间由 $N - 1$ 条道路连接。每条道路均可双向通行，且通过若干条道路，可以从任意城市到达其他任意城市。
- （条件 3）从城市 $0$ 出发，最多经过 $18$ 条道路即可到达任意其他城市。
每天，在 JOI 王国，许多人从城市 $0$ 出发前往其他城市。由于许多人有两个目的地，他们有时会提出以下查询：对于两个不同的城市 $X$、$Y$，以下哪一项（$0$）、（$1$）、（$2$）成立？
- （$0$）当我们从城市 $0$ 前往城市 $X$ 时，必定会经过城市 $Y$。
- （$1$）当我们从城市 $0$ 前往城市 $Y$ 时，必定会经过城市 $X$。
- （$2$）以上两项（$0$）和（$1$）均不成立。
注意，在上述情形中，（$0$）、（$1$）、（$2$）中恰好有一项成立。当 $X = 0$ 时，无论 $Y$ 取何值，我们均认为（$1$）成立；类似地，当 $Y = 0$ 时，无论 $X$ 取何值，我们均认为（$0$）成立。
已知，正如 JOI 王国的道路网络一样，上述条件 1–3 在其他国家也成立。在 JOI 王国，人们计划开发以下两台机器，以便它们也可在其他国家使用：
- （机器 1）给定城市数量 $N$ 和道路网络信息，该机器为每个城市分配一个编码。编码是一个介于 $0$ 到 $2^{60} - 1$（含）之间的整数。
- （机器 2）给定由机器 1 分配的两个不同城市 $X$、$Y$ 的编码，该机器回答查询。
若分配的编码为大整数，则处理起来较为困难。我们希望开发的机器能分配较小的值作为编码。
注意，当使用机器 2 时，城市数量 $N$ 和道路网络信息不会直接提供给机器。
**任务**
为了开发上述两台机器，请编写以下两个程序：
- 给定 JOI 王国内的城市数量 $N$ 和道路网络信息，第一个程序为每个城市分配一个编码。
- 给定由第一个程序分配的两个不同城市的编码，第二个程序回答针对这些城市的查询。
**实现细节**
你需要提交两个使用**相同编程语言**编写的文件。
第一个文件为 `Encoder.c` 或 `Encoder.cpp`，该文件实现机器 1。它应实现以下函数，并且程序应包含 `Encoder.h`。
- `void Encode(int N, int A[], int B[])`
对于每个测试用例，该函数被调用一次。
- 参数 $N$ 表示城市数量。
- 参数 $A[]$、$B[]$ 是长度为 $N - 1$ 的整数序列，用于描述道路网络。元素 $A[i]$、$B[i]$（$0 \le i \le N - 2$）表示城市 $A[i]$ 与城市 $B[i]$ 之间有一条直接相连的道路。
你的程序应调用以下函数：
- `void Code(int city, long long code)`
该函数为城市分配编码。
- 参数 `city` 是被分配编码的城市编号，其值应为介于 $0$ 到 $N - 1$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被判定为 **Wrong Answer[1]**。若使用相同的参数调用该函数两次，你的程序将被判定为 **Wrong Answer[2]**。
- 参数 `code` 是分配给编号为 `city` 的城市的编码，其值应为介于 $0$ 到 $2^{60} - 1$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被判定为 **Wrong Answer[3]**。
你的程序应恰好调用函数 `Code` $N$ 次。若函数 `Encode` 结束时调用 `Code` 的次数不为 $N$，你的程序将被判定为 **Wrong Answer[4]**。
若对函数 `Encode` 的调用被判定为错误答案，你的程序将立即终止。
第二个文件为 `Device.c` 或 `Device.cpp`，该文件实现机器 2。它应实现以下函数，且程序应包含 `Device.h`。
- `void InitDevice()`
该函数初始化机器 2。函数 `InitDevice` 在调用以下函数 `Answer` 之前被调用一次。
- `int Answer(long long S, long long T)`
该函数回答每个查询。对于每个查询，函数 `Answer` 被调用一次。
- 参数 $S$、$T$ 是由函数 `Encode` 分配给两个不同城市 $X$、$Y$ 的编码。
- 为回答查询，函数 `Answer` 的返回值应满足以下条件：
- 若从城市 $0$ 前往城市 $X$ 时必定经过城市 $Y$，则返回值应为 $0$。
- 若从城市 $0$ 前往城市 $Y$ 时必定经过城市 $X$，则返回值应为 $1$。
- 否则，返回值应为 $2$。
因此，函数 `Answer` 的返回值应为介于 $0$ 到 $2$（含）之间的整数。若返回值超出此范围，你的程序将被判定为 **Wrong Answer[5]**。若返回值在此范围内但不满足上述条件，你的程序将被判定为 **Wrong Answer[6]**。
**评分流程**
评分按以下方式进行。若你的程序被判定为错误答案，则立即终止。
（1）函数 `Encode` 被调用一次。
（2）函数 `InitDevice` 被调用一次。
（3）对于每个测试用例，机器 2 会收到 $Q$ 个查询。对于第 $j$ 个查询（$1 \le j \le Q$），函数 `Answer` 被调用，其参数 $S$ 为 $S_j$，参数 $T$ 为 $T_j$，其中 $S_j$、$T_j$ 分别是由函数 `Encode` 分配给城市 $X_j$、$Y_j$ 的编码。
（4）你的程序被视为正确。
**重要提示**
- 运行时间和内存使用量根据评分流程中的（1）、（2）、（3）计算。注意，在流程（3）中，函数 `Answer` 总共被调用 $Q$ 次。
- 你的程序在流程（1）中调用函数 `Encode`、在流程（2）中调用函数 `InitDevice`、或在流程（3）中调用函数 `Answer` 时，均不得被判定为 **Wrong Answer**。你的程序必须在无运行时错误的情况下执行。
- 你的程序可以为内部使用实现其他函数，或使用全局变量。提交的程序将与评分器一起编译，并生成一个可执行文件。所有全局变量和内部函数应声明为 `static`，以避免与其他文件发生冲突。机器 1 和机器 2 的程序在评分时将作为两个独立的进程运行，它们不能共享全局变量。
- 你的程序不应使用标准输入和标准输出。你的程序不得通过任何方式与其他文件通信。
**编译与测试运行**
你可以从竞赛网页下载一个归档文件，其中包含一个用于测试你程序的示例评分器。该归档文件还包含你程序的一个示例源文件。
示例评分器由一个源文件组成，该源文件为 `grader.c` 或 `grader.cpp`。例如，若你的程序为 `Encoder.c` 和 `Device.c`，或 `Encoder.cpp` 和 `Device.cpp`，你可以运行以下命令来编译你的程序：
- **C**
`gcc -std=c11 -O2 -o grader grader.c Encoder.c Device.c -lm`
- **C++**
`g++ -std=c++14 -O2 -o grader grader.cpp Encoder.cpp Device.cpp`
当编译成功后，将生成可执行文件 `grader`。注意，实际评分器与示例评分器不同。示例评分器将以单个进程形式运行，它将从标准输入读取输入数据，并将结果写入标准输出。
输入格式
示例评分器从标准输入读取以下数据：
- 第一行包含两个以空格分隔的整数 $N$、$Q$。这表示共有 $N$ 个城市，以及给出 $Q$ 个查询。
- 接下来的 $N - 1$ 行中，第 $(i + 1)$ 行（$0 \le i \le N - 2$）包含两个以空格分隔的整数 $A_i$、$B_i$。这表示城市 $A_i$ 与城市 $B_i$ 之间有一条直接相连的道路。
- 接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含三个以空格分隔的整数 $X_j$、$Y_j$、$E_j$。这表示在第 $j$ 个查询中，$X = X_j$ 且 $Y = Y_j$；若你的程序对该查询的回答与 $E_j$ 不同，示例评分器将判定你的程序为 **Wrong Answer**。
输出格式
当程序成功终止时，示例评分器将以下信息写入标准输出。（引号实际不会输出。）
- 若你的程序被视为正确，示例评分器将以如下格式输出所分配编码的最大值：“Accepted : max_code=123456”。
- 若你的程序被视为错误答案，示例评分器将以如下格式输出其错误类型：“Wrong Answer [1]”。
若你的程序被视为多种类型的错误答案，示例评分器仅报告其中一种。
说明/提示
### 样例 1 解释
函数 `Encode(...)` 将使用以下参数被调用：
| 参数 | `Encode(...)` |
|:------:|:--------------------:|
| $N$ | $6$ |
| $A$ | $\{4, 0, 4, 3, 3\}$ |
| $B$ | $\{1, 3, 5, 2, 4\}$ |
| Machine 1 | Machine 2 |
|:-------------------:|:-----------------:|
| `Encode(...)` | |
| `Code(0,0)` | |
| `Code(2,4)` | |
| `Code(4,16)` | |
| `Code(1,1)` | |
| `Code(3,9)` | |
| `Code(5,25)` | |
| | `InitDevice()` |
| | `Answer(4,16)` |
| | `Answer(1,0)` |
| | `Answer(25,1)` |
| | `Answer(25,9)` |
| | `Answer(16,1)` |
### 数据范围
所有输入数据满足以下条件。关于 $N$、$Q$、$A_i$、$B_i$、$X_j$、$Y_j$ 的含义，请参见“示例评分器的输入”。
- $2 \le N \le 250000$。
- $1 \le Q \le 250000$。
- $0 \le A_i \le N - 1$（$0 \le i \le N - 2$）。
- $0 \le B_i \le N - 1$（$0 \le i \le N - 2$）。
- $A_i \ne B_i$（$0 \le i \le N - 2$）。
- 从城市 $0$ 出发，最多经过 $18$ 条道路即可到达任意其他城市。
- $0 \le X_j \le N - 1$（$1 \le j \le Q$）。
- $0 \le Y_j \le N - 1$（$1 \le j \le Q$）。
- $X_j \ne Y_j$（$1 \le j \le Q$）。
### 子任务
共有 2 个子任务。每个子任务的得分及额外约束如下：
**子任务 1 [8 分]**
- $N \le 10$。
**子任务 2 [92 分]**
无额外约束。在本子任务中，得分按如下方式计算：
- 设 $L$ 为本子任务所有测试用例中分配给城市的编码的最大值。
- 本子任务的得分为：
- 若 $2^{38} \le L$，得 $0$ 分。
- 若 $2^{36} \le L \le 2^{38} - 1$，得 $10$ 分。
- 若 $2^{35} \le L \le 2^{36} - 1$，得 $14$ 分。
- 若 $2^{34} \le L \le 2^{35} - 1$，得 $22$ 分。
- 若 $2^{28} \le L \le 2^{34} - 1$，得 $\lfloor 372 - 10 \log_2(L + 1) \rfloor$ 分。其中，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。
- 若 $L \le 2^{28} - 1$，得 $92$ 分。
请注意，若 $2^{38} \le L$，本子任务的结果在竞赛系统中可能显示为“Accepted : 0 points”或“Wrong Answer”。
翻译由 Qwen3-235B 完成