Background

This is an interactive problem.

Before submitting this problem, be sure to read the following carefully.

This problem only supports C++ submissions (C++14 is recommended; please do not use C++14 (GCC9)).

Due to Luogu’s special interaction mechanism, when submitting this problem, please remove the line #include "ds.h" from your code, and paste the following content at the very beginning of your code, then submit:

#include <vector>
void exchange(int x, int y);
int query(int u);
void answer(std::vector<int> par, std::vector<int> val);

If you encounter any unexpected situation when submitting this problem, please contact an administrator.

Problem Description

As an experienced OI contestant, you are already very familiar with all kinds of data structure problems. In contests, whenever you see a data structure problem, you can solve it quickly and easily. One day, you open an OJ and see this problem:

Given a rooted tree with $n$ nodes, nodes are numbered $1, 2, \dots, n$, and node $1$ is the root. Each edge has a weight from $1$ to $n - 1$, and these weights are pairwise distinct. Maintain a data structure that supports swapping the weights of the two edges whose weights are $x$ and $y$, and querying the maximum edge weight on the path from the root to node $u$.

Such a simple and classic tree problem is nothing difficult for you. Tired of maintaining updates and answering queries, you decide to switch roles. This time, you are the one asking questions, and you need to design suitable operations to extract the hidden data of the problem.

More specifically, now you do not know the tree structure, nor the initial edge weights. You need to obtain the tree structure and the initial weight of every edge through the following two operations:

1. Given positive integers $x, y$, where $1 \le x, y < n$, $x \neq y$, swap the weights of the two edges whose weights are $x$ and $y$.
2. Given a positive integer $u$, where $2 \le u \le n$, obtain the maximum edge weight among all edges on the path from node $1$ to node $u$.

The problem guarantees that the tree shape and every edge weight are fixed in advance, and will not be generated dynamically based on your operations.

[Implementation Details]

You need to include the header file #include "ds.h". You can call the following functions to interact with the interaction library:

void exchange(int x, int y);

• This function corresponds to operation $1$, meaning swapping the weights of the two edges whose weights are $x$ and $y$.
• You must ensure $1 \le x, y < n$, $x \neq y$.

int query(int u);

• This function corresponds to operation $2$, returning the maximum edge weight among all edges on the path from node $1$ to node $u$.
• You must ensure $2 \le u \le n$.

void answer(std::vector<int> par, std::vector<int> val);

• This function is used to submit your final answer, with the following format:
  • par is an array of length $n - 1$, where par[i] is the parent index of node $i + 2$, where $0 \le i \le n - 2$.
  • val is also an array of length $n - 1$, where val[i] is the initial weight of the edge between node $i + 2$ and its parent, where $0 \le i \le n - 2$.
• You must call this function exactly once!

You do not need to, and should not, implement the main function. In this problem, you only need to implement the following function:

void solve(int n, int lim1, int lim2);

• Here, $n$ is the number of nodes in the tree, $lim1$ is the operation limit for operation $1$, and $lim2$ is the operation limit for operation $2$.
• In the final test, for each test case, the interaction library will call solve exactly once, and score your solution based on whether your call to answer is correct.

In the attachments, we provide sample.cpp for your reference. You may implement your program based on it.

[How to Test with the Local Grader]

The attachments provide grader.cpp. The interaction library used in the final test is different from the provided local interaction library, so your implementation must not rely on the specific implementation details of the provided library.

You need to place your program ds.cpp together with grader.cpp and ds.h in the same directory, and compile in that directory using the following command to obtain the executable ds(.exe):

g++ -o ds ds.cpp grader.cpp -O2 -std=c++14 -lm

The attachments also provide compile.sh, whose content is this compile command. You can run it to compile, or copy the compile command from it to compile.

The executable reads input from standard input in the following format:

• The first line contains three positive integers $n, lim1, lim2$, representing the number of nodes in the tree, the limit for operation $1$, and the limit for operation $2$. The interaction library guarantees it can handle $2 \le n \le 500000$. For $n > 500000$, correct execution is not guaranteed.
• The second line contains $n - 1$ positive integers $p_2, p_3, \dots, p_n$, where $p_i$ is the parent index of node $i$. You must ensure $1 \le p_i \le n$, and the input provides a valid tree structure.
• The third line contains $n - 1$ positive integers $v_2, v_3, \dots, v_n$, where $v_i$ is the weight of the edge from node $i$ to $p_i$. You must ensure that $v_2, v_3, \dots, v_n$ form a permutation of $1$ to $n - 1$.
• When testing locally, be sure your input format meets the requirements; otherwise we do not guarantee that the interaction library will run normally.

If your input is valid and there is no runtime error, the provided interaction library will output the following messages based on your calls:

• If any call to exchange violates $1 \le x, y < n$, $x \neq y$, it outputs: Invalid call of exchange(x, y)! .
• If the number of calls to exchange exceeds $lim1$, it outputs: Too many exchanges! .
• If any call to query violates $2 \le u \le n$, it outputs: Invalid call of query(u)! .
• If the number of calls to query exceeds $lim2$, it outputs: Too many queries! .
• After outputting any of the above error messages, the interaction library terminates immediately.
• The interaction library outputs a prompt message every time you call answer:
  • If the length of par or val is not $n - 1$, it outputs Invalid output! .
  • If the par array differs from the tree structure, it reports the first wrong position and returns: The answer to p[i] is wrong! The right answer is j, but you output k. . Note that here $2 \le i \le n$, $j = p_i$ is the true parent of node $i$, and $k =$ par[i - 2] is what you output.
  • If par is correct but val differs from the initial edge weights, it reports the first wrong position and returns: The answer to v[i] is wrong! The right answer is j, but you output k. . Similarly, here $2 \le i \le n$, $j = v_i$ is the true initial weight of the edge from node $i$ to its parent, and $k =$ val[i - 2] is what you output.
  • If both par and val are correct, the interaction library outputs the number of times you called exchange and query. The output format is: Right output! cnt1 = A, cnt2= B. , where $A$ is the number of calls to exchange, and $B$ is the number of calls to query.
• When using the provided local interaction library, you may test your program by calling answer multiple times. However, for the code you submit, if you call answer more than once, you will only get $0$ points.

Your program should not read from or write to standard input/output; otherwise it will be considered an attack on the interaction library.

Input Format

See [How to Test with the Local Grader].

Output Format

See [How to Test with the Local Grader].

3 100 100
1 2
2 1

Right output! cnt1 = 2, cnt2 = 5.

见附件中的 ds2.in

见附件中的 ds2.ans

见附件中的 ds3.in

见附件中的 ds3.ans

见附件中的 ds4.in

见附件中的 ds4.ans

见附件中的 ds5.in

见附件中的 ds5.ans

见附件中的 ds6.in

见附件中的 ds6.ans

见附件中的 ds7.in

见附件中的 ds7.ans

Hint

[Sample Explanation #1]

One possible input is as follows:

• The parent of node $2$ is $1$, and the initial weight of the edge from $1$ to $2$ is $2$.
• The parent of node $3$ is $2$, and the initial weight of the edge from $2$ to $3$ is $1$.

One possible interaction process is as follows:

• Call query(2), returns $2$.
• Call exchange(1, 2). Now, the weight of edge $1$ to $2$ is $1$, and the weight of edge $2$ to $3$ is $2$.
• Call query(2), returns $1$. Now we can know that $1$ and $2$ are directly connected.
• Call query(3), returns $2$.
• Call exchange(1, 2).
• Call query(3), returns $2$. Now we can deduce that $2$ and $3$ are directly connected.
• Call query(2), returns $2$. Now we can deduce that after the two exchange operations, the weight of edge $1$ to $2$ is $2$, and the weight of the edge from $2$ to $3$ is $1$.
• Call answer([1, 2], [2, 1]), and terminate the program.

[Sample Explanation #2]

This sample satisfies $n \le 50$ and Special Property A.

[Sample Explanation #3]

This sample satisfies $n \le 1000$.

[Sample Explanation #4]

This sample satisfies $n \le 20000$ and Special Property B.

[Sample Explanation #5]

This sample satisfies $n \le 100000$ and Special Property A.

[Sample Explanation #6]

This sample satisfies $n \le 100000$.

[Sample Explanation #7]

This sample satisfies $n \le 500000$.

[Constraints]

Test Point	$n=$	$lim1=$	$lim2=$	Special Property
$1$	$10$	$1000001$		A
$2$
$3$	$50$	$1000002$
$4$
$5$	$600$	$3000003$
$6$
$7$	$1000$	$1100004$	$2200004$
$8$		$1100005$	$2200005$
$9$
$10$	$20000$	$3000006$		B
$11$
$12$
$13$	$100000$	$3000007$		A
$14$
$15$		$3000008$
$16$
$17$
$18$	$500000$	$3500009$		A
$19$
$20$		$3500010$		B
$21$
$22$		$3500011$
$23$
$24$
$25$

Special Property A:

• Each node has at most $1$ child, i.e. the tree is a chain.
• The labels of non-root nodes on the chain are uniformly random among all possible labelings.
• The edge-weight permutation is uniformly random among all $(n - 1)!$ possible permutations.

Special Property B:

• The tree shape is generated randomly as follows:
  • First, for each $2 \le i \le n$, choose the parent of node $i$ uniformly at random among the integers in $[1, i - 1]$.
  • Then uniformly randomly shuffle the labels of non-root nodes, obtaining the final labeled rooted tree structure.
• The edge-weight permutation is uniformly random among all $(n - 1)!$ possible permutations.

You can determine which special property the testdata satisfies based on the values of $lim1, lim2$.

[Scoring]

This problem is first subject to the same restrictions as traditional problems. For example, compilation errors result in $0$ points for the whole problem; runtime errors, exceeding the time limit, exceeding the memory limit, etc. result in $0$ points for the corresponding test points. You may only access variables you define and those provided by the interaction library, and their corresponding memory; attempting to access other memory may cause compilation errors or runtime errors.

Under the above conditions, you can obtain the score for a test point if and only if the parameter format of every call is correct, the number of calls to exchange does not exceed $lim1$, the number of calls to query does not exceed $lim2$, and the par and val arrays given in your first call to answer are correct.

It is guaranteed that, in both the provided interaction library and the final judging interaction library, the worst-case complexity of a single call to exchange and query is $O(\log n)$. Under the problem limits, the interaction library runs within $4$ seconds and uses at most $256$ MB of memory.

That is, you have at least $4$ seconds of time and $768$ MB of memory available.

[Reminder]

We remind you again: the tree shape and every edge weight are fixed in advance, and will not be generated dynamically based on your operations.

You need to pay attention to your program’s time cost and memory cost.

Gaining points by accessing input/output files, attacking the judging system, or attacking the judging library is considered cheating, and the score obtained will be invalid.

Translated by ChatGPT 5