PUMA

题目背景

一只野生黑色美洲狮出现在舒门附近的自然公园中。市政府派出了 $K$ 名动物学家，希望把它抓住。

为简化问题，公园中有 $N$ 个主要地点，编号为 $0$ 到 $N-1$。这些地点由 $N-1$ 条双向小路连接，并且任意两个地点之间都可以通过这些小路互相到达。也就是说，公园的结构是一棵树。两个地点之间若有一条小路直接相连，则称它们相邻。

政府希望每个地点都被至少一名动物学家调查。每名动物学家都从公园入口，即 $0$ 号地点开始，沿小路移动，并且不能再次访问自己已经调查过的地点。当他到达一个再也无法前进的位置时，就会离开公园。这样的地点称为出口。

出于安全考虑，任意时刻公园里只能有一名动物学家。动物学家之间存在竞争，因此他们约定，彼此之间唯一的“通信”方式是：可以在地点上留下一个整数标记，标记值范围为 $0$ 到 $M$。初始时，所有地点的标记均为 $0$。

动物学家会一个接一个进入公园，但顺序事先未知。由于公园地图被偷走了，当一名动物学家位于某个地点时，他只知道：

• 自己是从哪个地点来的；
• 当前地点的编号和当前地点的标记；
• 所有相邻地点的标记，但看不到这些相邻地点的编号。

请帮助动物学家设计策略，使得所有地点都能被至少一名动物学家调查。

题目保证：$K$ 恰好等于出口数量，并且给定的 $M$ 足够大，存在合法策略。

提交方式

本题是 通信 / 函数式提交题。选手不需要读写标准输入输出，也不要自己写 main。

你需要实现下面的函数：

void zoologist(int N, int K, int M, std::vector<int> p, int m, std::vector<int> a);

参数含义如下：

• N：地点数量；
• K：动物学家数量；
• M：标记的最大值，标记必须是 $0$ 到 $M$ 之间的整数；
• p：长度为 $N$ 的数组，表示树的结构。对于 $1\le i\le N-1$，地点 p[i] 与地点 i 之间有一条小路，且 p[0] = -1；
• m：当前 $0$ 号地点的标记；
• a：$0$ 号地点所有相邻地点的标记，顺序任意。

评测时，该函数会被调用 $K$ 次，每名动物学家调用一次。调用是顺序进行的：第一名动物学家完成后，再以当前标记状态调用第二名动物学家，依此类推。

不同动物学家的调用可能位于不同进程中，也可能复用同一进程。因此，你的程序不能依赖全局变量在不同调用之间保存信息。动物学家之间唯一可靠的信息传递方式是地点上的标记。

可调用函数

在 zoologist 中，你可以调用如下两个函数。

修改当前地点标记

void set_marking(int m);

将当前地点的标记改为 m。要求 $0\le m\le M$。

移动到相邻地点

std::pair<int, std::vector<int>> movement(int i);

参数 i 表示选择第 i 条可走小路。这里的编号是相对于当前能看到的相邻地点标记数组而言的：

• 一开始，相邻地点标记数组就是传入 zoologist 的参数 a；
• 每次调用 movement 后，返回值的第二个元素会成为新的相邻地点标记数组；
• 这些标记的顺序是任意的。

movement(i) 返回一个二元组：

• 第一项：移动后所在地点的编号；
• 第二项：移动后当前位置的所有可继续前往的相邻地点的标记，不包含刚刚来的那个地点，顺序任意。

如果当前动物学家已经到达出口，应直接结束 zoologist 函数，表示离开公园。

Hydro 提交说明

本配置包采用 函数式提交 + 隐藏本地 grader 的方式在 Hydro OJ 上测评。选手不需要读写标准输入输出，也不要自己写 main。提交代码建议写成：

#include "puma.h"
using namespace std;

void zoologist(int N, int K, int M, vector<int> p, int m, vector<int> a) {
    // 实现你的策略
}

#include "grader.cpp"

其中 puma.h 与 grader.cpp 由题目下发。隐藏 grader 会顺序调用 zoologist 共 $K$ 次，并检查是否所有地点最终都被至少一名动物学家调查。

题意仍要求：不要依赖全局变量在不同动物学家调用之间传递信息；可靠通信方式应只有地点上的标记。

约束条件

• $1\le N\le 1000$；
• $K$ 等于出口数量；
• 对于给定的 $M$，保证存在合法策略。

子任务

记 $C$ 为一名动物学家从地点 $0$ 出发最多能经过的小路数量。

子任务	分值	依赖	$M$	其他限制
0		无	无	样例
1	6		$M=1$	地点 $0$ 与所有其他地点直接相连
2	14		$M=N$	无
3	15	子任务 0	$M=C$	$N=2^s-1$，地点 $0$ 有两个相邻地点，$2^{s-1}-2$ 个地点有三个相邻地点，其余地点只有一个相邻地点
4	18	子任务 0、3		向量 $p$ 中除 $-1$ 外没有唯一值
5	47	子任务 0～4	无

样例说明

考虑下图中的公园结构：

对应的树为：

0
├── 1
│   ├── 3
│   └── 4
└── 2
    ├── 5
    └── 6

即：

N = 7, K = 4, M = 4
p = {-1, 0, 0, 1, 1, 2, 2}

下面是一种可能的执行过程。

第一名动物学家：

你的操作	grader 行为
zoologist(7,4,4,{-1,0,0,1,1,2,2},0,{0,0})	调用函数
set_marking(1)	将地点 0 标记为 1
movement(0)	返回 {1,{0,0}}
movement(1)	返回 {4,{}}
set_marking(2)	将出口处标记为 2

后续三名动物学家也可以根据已有标记选择未调查的分支，最终使所有地点都被至少调查一次。

本地调试

压缩包中提供的 grader.cpp 本身就是本地 grader。将你的代码按上述格式保存后，可以直接编译运行。

本配置的数据输入格式为：

• 第 1 行：三个整数 $N,K,M$；
• 第 2 行：$N$ 个整数，表示数组 $p$，其中 $p[0] = -1$。

程序运行结束后，grader 会输出 $N$ 个 0/1 标志，表示每个地点是否被调查；Hydro 的 SPJ 会要求这些标志全为 1。

@下发文件