Background

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

Problem Description

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).

Input Format

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<int> fa,vector<int> 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.

Output Format

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.

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

Hint

For all testdata, $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$, and for any $1\leq i < n$, $fa_i\geq 0$.

• Subtask 1 ($5$ points): $n\leq 1000$.
• Subtask 2 ($20$ points): $n\leq 200000$.
• Subtask 3 ($30$ points): $fa_i=i-1$.
• Subtask 4 ($45$ points): no special constraints.

The scoring for each subtask is the minimum score among all test points within that subtask. The interactive library runs in at most 600ms and uses at most 140MB of memory.

The time limit shown on the OJ is not the real time limit. If your code does not run normally within the required time and memory and correctly answers all queries, that test point gets 0 points. If the total running time of your functions is not less than 2400ms, you will get Time Limit Exceeded (in the actual test, this is implemented by making the grader loop forever). Otherwise, if the total running time is $x$ ($x<2400$) milliseconds, your score is:

• If $x\leq 1200$, return Accepted and get full points for that test point.
• If $1200<x<2400$, return Partially Correct and get $(\frac {2400 - x} {1200}) ^ 2$ times the score for that test point.

The time shown in the test point information is not the real running time; the one shown in the SPJ details is the running time of your implementation.

Source: NFLSPC #6 H by asmend

Translated by ChatGPT 5