P12919 [POI 2021/2022 R3] 投票表决 / Głosowanie【交互库暂未配置】

翻译来自于 [LibreOJ](https://loj.ac/p/4856)。

**题目译自 [XXIX Olimpiada Informatyczna – III etap](https://sio2.mimuw.edu.pl/c/oi29-3/dashboard/) [Głosowanie](https://szkopul.edu.pl/problemset/problem/BM4yZ7Mo9yZtUdXxVdZAkAjs/statement/)** 某公司总裁想通过举办「柑橘星期四」来提升员工士气，但他在采购橙子还是葡萄柚之间犹豫不决，最终决定让员工们自己投票选择。 投票将按照公司层级进行。公司共有 $n$ 名员工，编号从 $1$ 到 $n$，其中编号 $1$ 是总裁。每位员工要么是管理者，要么是普通员工，总裁必然是管理者。每位管理者直接领导奇数名下属，这些下属可能是普通员工或其他管理者。普通员工没有下属。除了总裁（没有上级）外，每位员工有且仅有一位直接上级。公司层级中不存在循环。 普通员工独立决定支持橙子还是葡萄柚，而管理者则跟随其直接下属的多数意见投票。最终结果由总裁的投票决定。 Bajtazar 是橙子批发商，希望橙子能在投票中获胜。然而，他的好友 Bajtoni 是葡萄柚批发商，更希望葡萄柚胜出。于是，两个好友决定玩一场游戏：从 Bajtazar 开始，他们轮流（每次一人）挑选一名尚未被说服的普通员工，劝说其支持自己的柑橘（Bajtazar 和 Bajtoni 都极具说服力）。游戏在所有普通员工都被说服后结束。 请你帮助字节扎尔制定策略，选择员工的顺序，确保橙子最终获胜。你可以假设公司层级设计总是能让字节扎尔无论 Bajtoni 如何选择都能胜出。 ### 交互方式 你需要编写一个程序，通过提供的库（模拟 Bajtoni 的行动）帮助 Bajtazar。 使用库的方法如下： - C/C++: `#include "glolib.h"` - Python: `from glolib import daj_n, daj_przelozonego, ruch` 库提供以下函数： - `daj_n()`：返回整数 $n$，表示公司员工总数。 - `daj_przelozonego(v)`：返回编号为 $v$ $(1 < v \leq n)$ 的员工的直接上级编号，上级编号总是小于员工编号。 - `ruch(x)`：通知库 Bajtazar 选择编号为 $x$ 的普通员工进行说服，返回 Bajtoni 接下来选择的员工编号。若 Bajtazar 的这次选择是游戏的最后一动，程序会在调用后自动结束（假设 Bajtazar 总是最后行动）。 `daj_n` 和 `daj_przelozonego` 可多次调用。你的程序不得打开文件或使用标准输入输出，但可使用标准错误输出（stderr），不过这会消耗时间。程序将与库一起编译，命令如下： - C++: `g++ -O3 -static -std=c++17 glolib.cpp glo.cpp` - Python: `python3 glo.py` 注意：内存限制仅适用于你的代码，不包括库的内存使用。

无

无

示例评测程序和交互库位于「文件」中。这些库的行为可能与正式评测不同，且未必符合任务假设，仅用于展示程序交互方式。 你的程序若与示例库编译，将从标准输入读取公司层级描述：先是 $n$，然后是 $n-1$ 个数 $p_{2}, \ldots, p_{n}$（用空格分隔），$p_{i}$ 表示编号 $i$ 的员工的上级编号。示例库中，字节尼总是选择未被说服的最小编号普通员工，这一策略也在样例和评测测试点中采用。示例库会输出字节扎尔和字节尼的每次行动。 以下是样例中程序的运行流程，公司层级如下图所示：  | 调用 | 返回值 | 说明 | |-----------------------|--------|--------------------------------------------------| | `daj_n()` | `7` | $n=7$ | | `daj_przelozonego(2)` | `1` | $2$ 的上级是 $1$ | | `daj_przelozonego(3)` | `2` | $3$ 的上级是 $2$ | | `daj_przelozonego(4)` | `1` | $4$ 的上级是 $1$ | | `daj_przelozonego(5)` | `1` | $5$ 的上级是 $1$ | | `daj_przelozonego(6)` | `2` | $6$ 的上级是 $2$ | | `daj_przelozonego(7)` | `2` | $7$ 的上级是 $2$ | | `ruch(3)` | `5` | Bajtazar 说服 $3$，Bajtoni 说服 $5$ | | `ruch(7)` | `4` | Bajtazar 说服 $7$，Bajtoni 说服 $4$，此后橙子无胜算 | | `ruch(6)` | | Bajtazar 说服 $6$，游戏结束，程序自动终止 | 若 Bajtazar 在第二步选择说服 $4$，则可确保橙子获胜。 **附加样例** 1. 该样例满足 $n=19$，总裁直接领导 $3$ 名管理者，每位管理者领导 $5$ 名普通员工； 2. 该样例满足 $n=364$，每位管理者直接领导 $3$ 人，所有普通员工与总裁的层级距离相等； 3. 该样例满足 $n=200000$，公司有 $100001$ 名管理者（除总裁外，每人上级为编号小 $1$ 的管理者），$99999$ 名普通员工直接受 $100001$ 号管理者领导。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $2 \leq n \leq 13$ | $20$ | | $2$ | $2 \leq n \leq 1000$| $40$ | | $3$ | $2 \leq n \leq 200000$ | $40$ |