P9932 [NFLSPC #6] 树

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

给定一棵 $n$ 个点的树，标号从 $0$ 到 $n-1$，每个点有一个 $0$ 到 $n-1$ 之间的颜色。 $q$ 次询问，每次查询 $x$ 的祖先中颜色为 $c$ 的点中离 $x$ 最近的一个（也就是深度最大的一个）的编号，**强制在线**。 **点的颜色在数据生成完之后进行了一次随机打乱（也就是作用了一个均匀随机的排列）**。

**由于本题输入量较大，我们采用交互题的方式进行评测**。 你不需要也不应该实现主函数 `main`，你需要实现以下两个函数： ``` extern "C" void init(int n,vector fa,vector 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 的输入输出格式，仅为测试使用，**你实现的函数不应该对标准输入输出流进行任何操作**。

对于所有数据，$2\leq n\leq 2\times 10^6$，$q=5n\leq 10^7$，$-1\leq fa_i