题目背景

请不要使用 C++14 (GCC 9) 提交

题目描述

给定一棵 $n$ 个点的树，标号从 $0$ 到 $n-1$，每个点有一个 $0$ 到 $n-1$ 之间的颜色。

$q$ 次询问，每次查询 $x$ 的祖先中颜色为 $c$ 的点中离 $x$ 最近的一个（也就是深度最大的一个）的编号，强制在线。

点的颜色在数据生成完之后进行了一次随机打乱（也就是作用了一个均匀随机的排列）。

输入格式

由于本题输入量较大，我们采用交互题的方式进行评测。

你不需要也不应该实现主函数 main，你需要实现以下两个函数：

extern "C" void init(int n,vector<int> fa,vector<int> col)

• $n$：节点的个数。
• $fa$：长度为 $n$ 的数组，$fa_i$ 表示节点 $i$ 的父亲。特别地，$fa_0=-1$。
• $col$：长度为 $n$ 的数组，$col_i$ 表示节点 $i$ 的颜色。再次强调：$col$ 在数据生成完之后进行了一次随机打乱。
• 这个函数会被调用恰好一次，它给了你树的信息。你可以在这次函数调用的时候计算一些需要用到的信息。

extern "C"  int query(int x,int c)

• $x$：查询的节点编号。
• $c$：查询的颜色。
• 你应该返回 $x$ 的祖先中离 $x$ 最近的颜色为 $c$ 的节点的编号。若不存在这样的节点，返回 -1。
• 这个函数恰好被调用 $q$ 次。
• 每次调用函数时你并不知道以后的询问，也就是说，询问是 强制在线 的。

使用下发 grader 测试代码时，输入格式为：

• 第一行输入两个数 $n,q$。
• 第二行输入 $n$ 个数 $fa_0,\cdots,fa_{n-1}$。
• 第三行输入 $n$ 个数 $col_0,\cdots,col_{n-1}$。
• 接下来 $q$ 行，每行两个数 $x,c$，表示一组询问。

输出格式

测试代码时，输出格式为：

• $q$ 行，每行一个数，表示答案。
• 接下来，下发 grader 会输出你的耗时（注意这里并不会检查正确性）。

注意：这里给出的输入输出格式为下发 grader 的输入输出格式，仅为测试使用，你实现的函数不应该对标准输入输出流进行任何操作。

5 25
-1 0 1 1 0
0 1 0 2 2
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4

0
-1
-1
-1
-1
0
1
-1
-1
-1
2
1
-1
-1
-1
0
1
3
-1
-1
0
-1
4
-1
-1

提示

对于所有数据，$2\leq n\leq 2\times 10^6$，$q=5n\leq 10^7$，$-1\leq fa_i<i$，$0\leq col_i<n$，$fa_0=-1$ 且对任意 $1\leq i < n$，$fa_i\geq 0$。

• 子任务 1（$5$ 分）：$n\leq 1000$。
• 子任务 2（$20$ 分）：$n\leq 200000$。
• 子任务 3（$30$ 分）：$fa_i=i-1$。
• 子任务 4（$45$ 分）：无特殊限制。

每个子任务评分方式为子任务内所有点的得分取最小值。交互库运行时长不超过 600ms，消耗空间不超过 140MB。

本题在 OJ 上显示的时限不是真正的时限。若你的代码没有在规定的时间和空间内正常运行并正确回答所有询问，该测试点获得 0 分。若你实现的函数运行时间不小于 2400ms，你将获得 Time Limit Exceeded（实际测试时会通过让 grader 死循环来实现这一点）。否则若你实现的函数共运行了 $x$（$x<2400$） 毫秒，你获得的分数为：

• $x\leq 1200$，返回 Accepted, 获得该测试点全部分数。
• $1200<x<2400$，返回 Partially Correct, 获得该测试点 $(\frac {2400 - x} {1200}) ^ 2$ 倍的分数。

测试点信息上显示的不是真正的耗时，SPJ 详细信息里显示的才是你实现的部分的耗时。

Source：NFLSPC #6 H by asmend