P9932 [NFLSPC #6] Tree

# Please do not submit using C++14 (GCC 9).

Given a tree with $n$ nodes, labeled from $0$ to $n-1$, each node has a color between $0$ and $n-1$. There are $q$ queries. For each query, you need to find, among the ancestors of $x$, the node whose color is $c$ and is closest to $x$ (i.e., with the greatest depth), and output its label. The queries are **strictly online**. **After the testdata is generated, the node colors are randomly shuffled once (i.e., a uniformly random permutation is applied).**

**Because the input size is large, this problem is judged as an interactive problem.** You do not need and should not implement the main function `main`. You need to implement the following two functions: ``` extern "C" void init(int n,vector fa,vector col) ``` * $n$: the number of nodes. * $fa$: an array of length $n$, where $fa_i$ is the parent of node $i$. In particular, $fa_0=-1$. * $col$: an array of length $n$, where $col_i$ is the color of node $i$. Emphasis again: **$col$ is randomly shuffled once after the testdata is generated**. * This function will be called exactly once, providing the tree information. You may precompute any needed information during this call. ``` extern "C" int query(int x,int c) ``` * $x$: the node to query. * $c$: the color to query. * You should return the label of the closest ancestor of $x$ whose color is $c$. If no such node exists, return `-1`. * This function is called exactly $q$ times. * When each call happens, you do not know future queries, so the queries are **strictly online**. When using the provided grader test code, the input format is: - The first line contains two integers $n,q$. - The second line contains $n$ integers $fa_0,\cdots,fa_{n-1}$. - The third line contains $n$ integers $col_0,\cdots,col_{n-1}$. - The next $q$ lines each contain two integers $x,c$, representing one query.

When running with the test code, the output format is: - $q$ lines, each containing one integer, the answer. - Then the provided grader will output your running time (note that correctness is not checked there). Note: the input/output format given here is the one used by the provided grader, only for local testing. **Your implemented functions should not perform any operations on standard input/output streams.**

For all testdata, $2\leq n\leq 2\times 10^6$, $q=5n\leq 10^7$, $-1\leq fa_i