题目描述

你是大鱼，你管理着一个巨大的国家。

这个国家之中有很多城市，城市之间也有很多河流，经过仔细的观察发现，每个城市都会流出一条河流，要么流向大海，要么流向另外一座城市，由于水总是往低处流动，所以不会出现一个河流构成的环，而且你发现流向大海的河流只有一条。

在某一个时刻，可能会有一场暴雨在某座城市上空降临，这座城市流出的河流会暴增，这座城市下游的城市流出的河流也都会暴增。

下暴雨的城市没有什么较好的防范办法，但是在下游的每一座城市，它们都可以在流向它们的其中一条河流做好准备。如果一个城市在一条流向它的河流做好了准备，它就可以避免这条河流暴增造成的巨大损害。

在一开始，你可以命令每座城市在一条流向它的河流做好准备（当然也可以不做任何准备）。在之后的每场暴雨前后，由于时间紧急，所以你只能发出一些紧急命令。紧急命令有两种：

1. 令一座城市取消对流向它河流的准备。
2. 令一座城市在某一条流向它的河流做好准备。

由于人力资源的原因。你并不能让一座城市同时在两条河流做好准备，因此如果你想让一座已经在某条河流做好准备的城市在另一条河流做准备，你必须先取消它在当前河流的准备。

现在有 $q$ 场暴雨一场接着一场到来，你能在一场暴雨前观测到它将在哪座城市降临，在每场暴雨前你可以发出一些紧急命令来避免下游的城市收到巨大损害，你也可以在暴雨后发出一些紧急命令来做一些暴雨后的准备，当然，你希望发的紧急命令尽量少，你可以找到一个优秀的办法吗？

任务

你需要实现两个函数，以完成题目的任务：

• init(n, father):

• 这个函数将在任务一开始运行，且仅会调用一次，它将会告诉你这座国家的一些信息，你需要给出一开始每座城市做的准备。

• n 表示城市数量，城市编号为 $1$ 到 $n$。

• father 是一个长度为 $n - 1$ 的数组，下标为 $[0 \dots n-2]$，$father_i$ 表示城市 $i + 2$ 流出河流到达城市的编号，其中城市 $1$ 流出的河流流入大海，保证 $father_i < i + 2$。

• 返回一个长为 $n$ 的数组，表示每个城市一开始做出的准备，第 $i-1$ 个数表示第 $i$ 个城市一开始准备好来自这个城市的河流，若为 $0$ 则表示什么都没有准备。

• solve(x):

• 该函数可能会在调用 init 函数之后被调用多次，表示一场暴雨即将在城市 $x$ 袭来，你需要使用 set 函数发出紧急命令来避免下游城市的巨大损害。

• 你需要保证在这个函数中调用 set 函数次数不超过 $60$。

• 在这个函数中你应该调用 wait 函数恰好一次，在调用 wait 函数之前的发出命令将在暴雨来临前发出，在调用 wait 函数之后发出的命令将在暴雨来临后发出。

你可以调用以下两个函数来实现 solve。

• set(x, p):

• 仅可以在 solve 函数中调用，表示让 $x$ 城市在 $p$ 城市流出河流做好准备，如果 $p$ 为 $0$，那么代表让城市 $x$ 取消对流向他的河流的准备。

• 每次 solve 时最多调用 $60$ 次。

• 禁止在 init 函数中调用。

• wait()

• 在每次 solve 时恰好调用一次，表示你完成了暴雨前的准备，调用时必须保证此时暴雨来临该城市下游的城市都在流向它的河流做好准备。

• 该函数调用后可以继续操作，为下次暴雨做准备。

• 禁止在 init 函数中调用。

注意，一座城市要么不做任何准备，要么在一个城市到它的河流做好准备。

如果你的操作不合法或不满足要求，该测试点将立刻得到 $0$ 分。

如果有不清楚的地方，见样例及测评库下载，内附了样例程序。

实现细节

本题只支持 C++ 语言。

你只能提交一个源文件实现如上所述的 init、solve 函数，并且遵循下面的命名和接口。你需要包含头文件 river.h。

std::vector<int> init(int n, std::vector<int> father);
void solve(int x);

函数 set、wait 的接口信息如下。

void set(int x, int p);
void wait();

评测方式

下发的样例评测系统将读入一棵树和所有操作，格式如下：

第一行输入两个正整数 $n,q$，表示树的点数、询问数。

第二行 $n-1$ 个数表示 father 数组。

接下来 $q$ 行，每行一个数 $x$ 表示调用一次 solve(x)。

8 8
1 1 3 3 4 5 3
7
1
1
7
3
6
5
1

2 6
ok you are right!

限制与约定

$1\leq n \leq 50000$，$1 \leq q \leq 500000$。

你不能在一回合中调用超过 $60$ 次命令。

如果你在规定时间空间限制内没有完成任务，你将获得 $0$ 分。

不然，设 $x$ 为每次 solve 中调用 set 次数的最大值 $\max$，则你得到的分数为

$$f \left( x \right) = \begin{cases} 0 & 60 \lt x \\ 100 - 18 \times \sqrt{x - 35} & 36 \leq x \leq 60 \\ 100 & \operatorname{otherwise} \end{cases} $$

你的分数将会是所有测试点中分数的最小值。

若每次 solve 中 set 的调用次数不超过 $60$，且所有操作合法的话：

保证交互库用时不超过 $1\,\mathrm{s}$。

保证交互库使用空间不超过 $10\,\mathrm{MB}$。