{"raw_statement":[{"iden":"background","content":"请使用 C++ 20 提交。\n\n**不要**引入头文件，并在文件头加入以下内容：\n\n```cpp\nvoid SetID(int, int);\n```"},{"iden":"statement","content":"\n\n在 JOI 共和国中，有 $N$ 个机场，编号从 $0$ 到 $N - 1$。有 $N - 1$ 条航线，编号从 $0$ 到 $N - 2$。航线 $i$（$0 \\le i \\le N - 2$）双向连接机场 $U_i$ 与机场 $V_i$。通过若干条航线相连，可以从任意一个机场到达任意另一个机场。对每个机场，连接它与其他机场的航线数量至多为 $3$。\n\nBenjamin 计划在 JOI 共和国旅行。在旅程的最后一天，他想到达温泉所在的机场。游乐园位于机场 $x$，温泉位于机场 $y$。由于 Benjamin 对航线一无所知，他将与航空公司的工作人员 Ali 沟通。Benjamin 想知道：从游乐园所在的机场出发，到达温泉所在的机场，最少需要乘坐多少条航线。Ali 掌握航线信息，但 Benjamin 并不知道自己应当乘坐哪些航线。\n\n1. Ali 为每个机场设置一个 **ID 码**。ID 码是介于 $0$ 和 $2N + 19$（含）之间的整数。\n2. Benjamin 得到游乐园所在机场的 ID 码 $X$，以及温泉所在机场的 ID 码 $Y$。\n3. Benjamin 向 Ali 发送一封电子邮件。该邮件是一串长度 **恰好** 等于 $20$ 的字符串，字符串的每个字符均为 $0$ 或 $1$。\n4. Ali 给 Benjamin 回一封信。该信是一串长度在 $1$ 到 $300\\,000$（含）之间的字符串，字符串的每个字符均为 $0$ 或 $1$。\n\n请编写程序，实现航空公司工作人员 Ali 与旅客 Benjamin 的策略。注意：在第 $2$ 步中，Benjamin 能得到游乐园与温泉所在机场的 ID 码 $X, Y$，**然而 Benjamin 不能获得机场编号 $x, y$**。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/jd1zwpzu.png)\n\n### 实现细节\n\n你需要提交两个文件。\n\n#### `Ali.cpp`\n\n该文件应实现 Ali 的策略，并实现下述两个函数。程序应使用预处理指令 `#include` 引入 `Ali.h`。\n\n- `void Init(int N, std::vector<int> U, std::vector<int> V)`  \n  该函数用于为每个机场设置 ID 码（见「评分」中的场景说明），每个场景调用 **恰好一次**。\n  - 参数 $N$ 为 JOI 共和国中的机场数量。\n  - 参数 $U, V$ 为长度为 $N - 1$ 的数组，即 $U[i], V[i]$ 分别是航线 $i$（$0 \\le i \\le N - 2$）连接的机场 $U_i, V_i$。\n- `std::string SendA(std::string S)`  \n  该函数实现 Ali 给 Benjamin 的回信策略（见「评分」中的场景说明），在调用 `SendB`（见下文）之后、每个场景调用 **恰好一次**。\n  - 参数 $S$ 是长度为 $20$ 的字符串，即 Benjamin 发给 Ali 的电子邮件。\n  - 函数 `SendA` 应返回一个字符串，即 Ali 给 Benjamin 的回信。\n  - 返回值的长度必须在 $1$ 到 $300\\,000$（含）之间。若不满足，则判为 **Wrong Answer [5]**。\n  - 返回值的每个字符必须为 $0$ 或 $1$。若不满足，则判为 **Wrong Answer [6]**。\n\n对每次调用 `Init`，下述函数必须对每个机场调用一次，总计调用 $N$ 次：\n\n- `void SetID(int p, int value)`  \n  - 参数 $p$ 表示为机场 $p$ 设置 ID 码。必须满足 $0 \\le p \\le N - 1$。若不满足，则判为 **Wrong Answer [1]**。\n  - 参数 `value` 是 Ali 指定的该机场的 ID 码。必须满足 $0 \\le value \\le 2N + 19$。若不满足，则判为 **Wrong Answer [2]**。\n  - 不允许对同一个 $p$ 调用多次 `SetID`。若不满足，则判为 **Wrong Answer [3]**。\n  - 当 `Init` 结束时，`SetID` 的调用次数应为 $N$。若不满足，则判为 **Wrong Answer [4]**。\n\n一旦某次 `SetID` 调用被判为 Wrong Answer，程序将立即终止。\n\n#### `Benjamin.cpp`\n\n该文件应实现 Benjamin 的策略，并实现下述两个函数。程序应使用预处理指令 `#include` 引入 `Benjamin.h`。\n\n- `std::string SendB(int N, int X, int Y)`  \n  该函数实现 Benjamin 发给 Ali 的电子邮件策略（见「评分」中的场景说明），在 `Init` 调用之后、每个场景调用 **恰好一次**。\n  - 参数 $N$ 为 JOI 共和国中的机场数量。\n  - 参数 $X$ 为游乐园所在机场的 ID 码。\n  - 参数 $Y$ 为温泉所在机场的 ID 码。\n  - 函数 `SendB` 应返回 Benjamin 发给 Ali 的邮件字符串。\n  - 若返回值不是长度为 $20$ 的字符串，则判为 **Wrong Answer [7]**。\n  - 若返回值的任一字符不是 $0$ 或 $1$，则判为 **Wrong Answer [8]**。\n- `int Answer(std::string T)`  \n  该函数应计算从机场 $x$ 到机场 $y$ 的最少乘坐航线数（见「评分」中的场景说明），在 `SendA` 调用之后、每个场景调用 **恰好一次**。\n  - 参数 $T$ 为 Ali 发给 Benjamin 的回信字符串，长度在 $1$ 到 $300\\,000$（含）之间。\n  - 函数应返回从机场 $x$ 到机场 $y$ 所需的最少航线数量。\n\n### 重要注意事项\n\n- 程序可以实现其他内部使用的函数，或使用全局变量。提交的文件将与评测器一同编译，组成单个可执行文件。为避免与其他文件冲突，所有全局变量与内部函数都应声明在匿名命名空间中。评测时将分别作为 Ali 与 Benjamin 两个进程执行。Ali 进程与 Benjamin 进程 **不能共享** 全局变量。\n- 程序 **不得** 使用标准输入与标准输出。程序 **不得** 通过任何方式与其他文件通信。但你可以向标准错误输出调试信息。\n\n### 评分\n\n一个测试用例由 $Q$ 个场景组成，编号为 $0$ 到 $Q - 1$。每个场景给定如下数据（取值范围见「约束」）：\n\n- JOI 共和国的机场数量 $N$。\n- 游乐园所在的机场编号 $x$。\n- 温泉所在的机场编号 $y$。\n- 航线信息 $(U_0, V_0), (U_1, V_1), \\dots, (U_{N - 2}, V_{N - 2})$。\n\n对每个场景，依次调用 `Init`、`SendB`、`SendA`、`Answer`。你的程序应在这些调用中使用合法参数并返回合法值。调用顺序如下：\n\n1. 对 $k = 0, 1, \\dots, Q - 1$，依次执行步骤 $2$–$5$。\n2. 调用 `Init`，参数按场景 $k$ 的「实现细节」说明设置。\n3. 调用 `SendB`，参数按场景 $k$ 的「实现细节」说明设置。\n4. 调用 `SendA`，参数按场景 $k$ 的「实现细节」说明设置。\n5. 调用 `Answer`，参数按场景 $k$ 的「实现细节」说明设置。\n\n若程序在这些过程中任一处被判为 Wrong Answer，程序将立即终止，并视为未通过该测试用例。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/sfw8wp0j.png)\n\n### 编译与本地测试\n\n你可以从竞赛网页下载包含样例评测器的压缩包，用于本地测试。压缩包中也包含你程序的样例源文件。\n\n样例评测器文件名为 `grader.cpp`。为测试你的程序，请将 `grader.cpp`、`Ali.cpp`、`Benjamin.cpp`、`Ali.h`、`Benjamin.h` 放在同一目录下，并运行以下命令进行编译：\n\n```\ng++ -std=gnu++17 -O2 -o grader grader.cpp Ali.cpp Benjamin.cpp\n```\n\n若编译成功，将生成可执行文件 `grader`。\n\n注意：实际评测器与样例评测器不同。样例评测器作为单进程执行，从标准输入读取数据并向标准输出写出结果。"},{"iden":"input","content":"\n样例评测器从标准输入读取如下数据。所有输入值均为整数。\n\n> $Q$  \n>（场景 $0$ 的输入）  \n>（场景 $1$ 的输入）  \n>$\\vdots$  \n>（场景 $Q - 1$ 的输入）\n\n每个场景的输入格式如下：\n\n> $N$ $x$ $y$  \n> $U_0$ $V_0$  \n> $U_1$ $V_1$  \n>$\\vdots$  \n> $U_{N - 2}$ $V_{N - 2}$"},{"iden":"output","content":"\n如果程序被判为 Wrong Answer [1]–[8] 中的任意一种，样例评测器会输出其类型（引号仅为说明）：“Wrong Answer [1]”。\n\n否则，对每个场景，它会输出函数 `Answer` 的返回值以及 Ali 发给 Benjamin 的字符串的最大长度。样例评测器 **不会** 检查 `Answer` 的返回值是否正确。\n\n```\nScenario 0: Your Answer = 3\nScenario 1: Your Answer = 1\nScenario 2: Your Answer = 4\nScenario 3: Your Answer = 1\nScenario 4: Your Answer = 5\nAccepted: Maximum Length = 24\n```\n\n如果你的程序同时满足多种 Wrong Answer 的判定条件，样例评测器只报告其中一种。此外，即使你的程序在后续场景被判为 Wrong Answer [1]–[8]，只要在第一个场景未被判错，样例评测器也可能先输出如下中间结果：\n\n```\nScenario 0: Your Answer = 3\nScenario 1: Your Answer = 1\nScenario 2: Your Answer = 4\nWrong Answer [8]\n```"},{"iden":"note","content":"\n#### 约束\n- $1 \\le Q \\le 50$。\n- $2 \\le N \\le 10\\,000$。\n- $0 \\le U_i < V_i \\le N - 1$（$0 \\le i \\le N - 2$）。\n- $0 \\le x \\le N - 1$。\n- $0 \\le y \\le N - 1$。\n- $x \\ne y$。\n- 通过若干条航线相连，可以从任意一个机场到达任意另一个机场。\n- 对每个机场，连接它与其他机场的航线数量至多为 $3$。\n\n#### 子任务\n1.（$15$ 分）$Q = 1$。  \n2.（$85$ 分）$Q \\ge 2$。\n\n#### 子任务 1 的评分\n若你的程序在子任务 $1$ 的任意场景中被判为 Wrong Answer，则该子任务得分为 $0$。\n\n若你的程序正确回答子任务 $1$ 的所有测试用例，得分按下述规则计算。设 $L_1$ 为 Ali 发给 Benjamin 的字符串的最大长度。\n\n| $L_1$ 的取值 | 得分 |\n| :--- | :--- |\n| $150\\,001 \\le L_1 \\le 300\\,000$ | $7$ 分 |\n| $20\\,001 \\le L_1 \\le 150\\,000$ | $11$ 分 |\n| $L_1 \\le 20\\,000$ | $15$ 分 |\n\n#### 子任务 2 的评分\n若你的程序在子任务 $2$ 的任意场景中被判为 Wrong Answer，则该子任务得分为 $0$。\n\n若你的程序正确回答子任务 $2$ 的所有测试用例，得分按下述规则计算。设 $L_2$ 为 Ali 发给 Benjamin 的字符串的最大长度。**注意：若 $1\\,401 \\le L_2$，该子任务得分为 $0$。**\n\n| $L_2$ 的取值 | 得分 |\n| :--- | :--- |\n| $1\\,401 \\le L_2 \\le 300\\,000$ | $0$ 分 |\n| $71 \\le L_2 \\le 1\\,400$ | $52 - 35 \\times \\log_{10}\\!\\bigl(\\frac{L_2}{70}\\bigr)$ 分（向下取整） |\n| $45 \\le L_2 \\le 70$ | $87 - 0.5 \\times L_2$ 分（向下取整） |\n| $25 \\le L_2 \\le 44$ | $109 - L_2$ 分 |\n| $L_2 \\le 24$ | $85$ 分 |\n\n### 样例交互\n\n以下为样例评测器的样例输入与对应的函数调用。在该示例中，Ali 在 `Init` 中为机场 $0, 1, 2, 3$ 设置的 ID 码分别为 $12, 21, 25, 27$。\n\n#### 样例输入 1\n\n| Ali 的调用 | Ali 的返回值 | Benjamin 的调用 | Benjamin 的返回值 |\n| :--- | :--- | :--- | :--- |\n| $\\texttt{Init(4,[0,1,2],[1,2,3])}$ |  |  |  |\n| $\\texttt{SetID(0,12)}$ |  |  |  |\n| $\\texttt{SetID(1,21)}$ |  |  |  |\n| $\\texttt{SetID(2,25)}$ |  |  |  |\n| $\\texttt{SetID(3,27)}$ |  |  |  |\n|  |  | $\\texttt{SendB(12,25)}$ | $\\texttt{\"0000011111000011111\"}$ |\n| $\\texttt{SendA(\"00...11\")}$ | $\\texttt{\"10\"}$ |  |  |\n|  |  | $\\texttt{Answer(\"10\")}$ | $\\texttt{2}$ |\n\n在该样例中，有 $N (= 4)$ 个机场与三条航线：\n- 一条连接机场 $0$ 与机场 $1$ 的航线；\n- 一条连接机场 $1$ 与机场 $2$ 的航线；\n- 一条连接机场 $2$ 与机场 $3$ 的航线。\n\n从机场 $x (= 0)$ 到机场 $y (= 2)$ 至少需要乘坐 $2$ 条航线，因此 `Answer` 应返回 $2$。\n\n注意：`SendB` 的返回值并不是机场编号 $(x, y) = (0, 2)$，而是机场的 ID 码 $(X, Y) = (12, 25)$。\n\n#### 样例输入 2\n```\n2\n10 0 9\n0 1\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9\n15 12 8\n0 1\n0 2\n1 3\n1 4\n2 5\n2 6\n3 7\n3 8\n4 9\n4 10\n5 11\n5 12\n6 13\n6 14\n```\n在该样例中，$Q = 2$ 个场景：\n- 对于第一个场景，`Answer` 应返回 $9$。\n- 对于第二个场景，`Answer` 应返回 $6$。\n\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}