P9075 [WC/CTS2023] Tree Data Structure

**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: ```cpp #include void exchange(int x, int y); int query(int u); void answer(std::vector par, std::vector val); ``` If you encounter any unexpected situation when submitting this problem, please contact an administrator.

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: ```cpp 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$. ```cpp 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$. ```cpp void answer(std::vector par, std::vector 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: ```cpp 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)`: ```bash 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.**

See [How to Test with the Local Grader].

See [How to Test with the Local Grader].

**[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$|$1000001$|A| |$2$|$10$|$1000001$|$1000001$|A| |$3$|$50$|$1000002$|$1000002$|A| |$4$|$50$|$1000002$|$1000002$|A| |$5$|$600$|$3000003$|$3000003$|A| |$6$|$600$|$3000003$|$3000003$|A| |$7$|$1000$|$1100004$|$2200004$|A| |$8$|$1000$|$1100005$|$2200005$|| |$9$|$1000$|$1100005$|$2200005$|| |$10$|$20000$|$3000006$|$3000006$|B| |$11$|$20000$|$3000006$|$3000006$|B| |$12$|$20000$|$3000006$|$3000006$|B| |$13$|$100000$|$3000007$|$3000007$|A| |$14$|$100000$|$3000007$|$3000007$|A| |$15$|$100000$|$3000008$|$3000008$|| |$16$|$100000$|$3000008$|$3000008$|| |$17$|$100000$|$3000008$|$3000008$|| |$18$|$500000$|$3500009$|$3500009$|A| |$19$|$500000$|$3500009$|$3500009$|A| |$20$|$500000$|$3500010$|$3500010$|B| |$21$|$500000$|$3500010$|$3500010$|B| |$22$|$500000$|$3500011$|$3500011$|| |$23$|$500000$|$3500011$|$3500011$|| |$24$|$500000$|$3500011$|$3500011$|| |$25$|$500000$|$3500011$|$3500011$|| 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