P6541 [WC2018] Real-Time Strategy

### Special Note **Some notes for submitting this problem on Luogu (if there is any difference from the original statement, please follow this section):** 1. When submitting, please add the following function declaration in your program: ```cpp int explore(int,int); ``` 2. At the beginning of your program, you do not need to, and should not, include the `rts.h` header file. 3. Only `C++` (including `C++`, `C++11`, `C++14`, `C++17`) submissions are supported.

Little M is playing a Real Time Strategy game. Unlike most similar games, the map of this game is a tree. That is, the map can be represented by a connected graph with $n$ nodes and $n - 1$ edges. The nodes are numbered $1 \sim n$. Each node has two possible states: "known" or "unknown". When the game starts, only node $1$ is known. During the game, Little M can try to explore more nodes. Specifically, in each operation, Little M needs to choose a known node $x$, and an arbitrary node $y$ different from $x$ (node $y$ may be unknown). Then the game's automatic pathfinding system will give the second node $z$ on the shortest path from $x$ to $y$, i.e., the node adjacent to $x$ on the shortest path from $x$ to $y$. At this time, if node $z$ is unknown, Little M will mark it as known. The goal of the game is: using at most $T$ exploration operations, make all nodes become known. However, Little M is still a beginner at this game, and she hopes to get your help. **To make the game process easier, Little M provides you with an interactive library for this game; see "Task Description" and "Implementation Details".** **Also, Little M provides some hints; see the last section "Hint".** ### Task Description You need to implement a function `play` to help Little M achieve the goal. * `play(n, T, dataType)` * `n` is the number of nodes in the tree. * `T` is the limit on the number of exploration operations. * `dataType` is the data type of this test case; see "Constraints and Conventions". In each test case, the interactive library will call the `play` function exactly once. Before it is called, the game is at the initial state. You can call the function `explore` to help you explore more nodes in the game, but the number of calls to this function must not exceed $T$. * `explore(x, y)` * `x` is a known node. * `y` is any node different from $x$ (it does not have to be known). * This function returns the index of the second node on the shortest path from node $x$ to node $y$. After the function `play` returns, the interactive library will check the game state: only if every node is known will the goal be considered completed. ### Implementation Details You must submit exactly one source file `rts.cpp/c/pas` implementing the above function, and follow the naming and interface below. **For C/C++ users:** The source code needs to include the header file `rts.h` (**note that when submitting on Luogu, you do not need to include this header file**). The function `play` you need to implement: ``` void play(int n, int T, int dataType); ``` The interface of the function `explore` is: ``` int explore(int x, int y); ``` **For Pascal users:** You need to use the unit `graderhelperlib`. The function `play` you need to implement: ``` procedure play(n, T, dataType : longint); ``` The interface of the function `explore` is: ``` function explore(x, y : longint) : longint; ```

The first line contains three integers $n$, $T$, $\texttt{dataType}$. It is guaranteed that $2 \leqslant n \leqslant 3 \times 10^5$, $1 \leqslant T \leqslant 5 \times 10^6$, and $\texttt{dataType} = 1$ or $2$ or $3$. The next $n - 1$ lines each contain two integers $u$, $v$. It is guaranteed that $1 \leqslant u, v \leqslant n$ and $u \ne v$, representing an edge between $u$ and $v$. The input guarantees that these $n - 1$ edges form a tree.

The interactive library will judge whether the game goal is completed. If completed, it will output $\texttt{Correct}$; otherwise, it will output the corresponding error message.

### Sample Explanation This is the output file obtained using the grader in the problem directory and a correct program. For this sample, one possible call sequence of the `explore` function is: * `explore(1, 2)`, returns 3 * `explore(3, 2)`, returns 2 * `explore(2, 4)`, returns 3 * `explore(3, 4)`, returns 4 ### How to Test Your Program **For C/C++ users:** In the problem directory, you need to compile to an executable using the following command: `g++ grader.cpp rts.cpp -o rts -O2` The executable will read input from **standard input**. After reading is finished, the interactive library will call the `play` function. If at this time the number of times you call `explore` exceeds $T$, the interactive library will output detailed error information and exit. Then the interactive library will check whether the game goal is completed. If completed, it will output "$\texttt{Correct}$"; otherwise, it will output the corresponding error message. If the parameters passed to `explore` are invalid ($x, y$ are not in the range $1$ to $n$, or $x$ is not a known node, or $x = y$), then the interactive library will output detailed error information and exit. If you want to test using your own input file, please ensure that the input file meets the above format requirements. Otherwise, the program is not guaranteed to run correctly. ### How to Use the Sample Source Code In the problem directory, there are sample source codes for each language: `rts_sample.cpp/c/pas`. Choose the language you need, copy it as `rts.cpp/c/pas`, and compile as described above to obtain an executable. For unofficial participants, you can only choose one language to answer. That is, in the problem directory, you cannot have multiple versions of `rts.cpp/c/pas` in different languages at the same time; otherwise, the system will arbitrarily select one source file for judging and use it as the final result. Next, you need to modify the implementation of this file to meet the requirements of the problem. ### Subtasks There are 20 test points in total, and each test point is worth 5 points. For all test points and all samples, $2 \leqslant n \leqslant 3 \times 10^5$, $1 \leqslant T \leqslant 5 \times 10^6$, and $\texttt{dataType} = 1$ or $2$ or $3$. The data types corresponding to different $\texttt{dataType}$ are as follows: * For test points with $\texttt{dataType} = 1$, there are no special restrictions. * For test points with $\texttt{dataType} = 2$, the game map is a complete binary tree rooted at node $1$. That is, there exists a permutation $a$ of $1$ ~ $n$ such that $a_1 = 1$, and node $a_i$ ($1 < i \leqslant n$) is connected by an edge to node $a_{\lfloor i/2 \rfloor}$. * For test points with $\texttt{dataType} = 3$, the game map is a chain. That is, there exists a permutation $a$ of $1$ ~ $n$ such that node $a_i$ ($1 < i \leqslant n$) is connected by an edge to node $a_{i-1}$. For each test point, the values of $n$, $T$, and $\texttt{dataType}$ are as follows: | Test Point ID | $n =$ | $T =$ | $\texttt{dataType} =$ | |-|-|-|-| | 1 | $2$ | $10000$ | 1 | | 2 | $3$ | $10000$ | 1 | | 3 | $10$ | $10000$ | 1 | | 4 | $100$ | $10000$ | 1 | | 5 | $1000$ | $10000$ | 2 | | 6 | $20000$ | $300000$ | 2 | | 7 | $250000$ | $5000000$ | 2 | | 8 | $1000$ | $20000$ | 3 | | 9 | $5000$ | $15500$ | 3 | | 10 | $30000$ | $63000$ | 3 | | 11 | $150000$ | $165000$ | 3 | | 12 | $250000$ | $250100$ | 3 | | 13 | $300000$ | $300020$ | 3 | | 14 | $1000$ | $50000$ | 1 | | 15 | $5000$ | $200000$ | 1 | | 16 | $30000$ | $900000$ | 1 | | 17 | $150000$ | $3750000$ | 1 | | 18 | $200000$ | $4400000$ | 1 | | 19 | $250000$ | $5000000$ | 1 | | 20 | $300000$ | $5000000$ | 1 | ### Hint Here are some thoughtful tips from Little M: * A graph (undirected graph) consists of nodes and edges. An edge is an unordered pair of nodes, used to describe the relationships between nodes. * A path is a non-empty sequence of nodes such that there is an edge between every two adjacent nodes in the sequence. * Two nodes are connected if and only if there exists a path that starts at one of them and ends at the other. * A graph is connected if and only if every pair of nodes in the graph is connected. * A tree with $n$ nodes is a connected graph with $n$ nodes and $n - 1$ edges. * The shortest path between two nodes means, among all possible paths connecting these two nodes, the one with the smallest sequence length. * In a tree, the shortest path between any two nodes is unique. * Gaining points by accessing input/output files, attacking the judging system, attacking the judging library, etc., is considered cheating, and the score obtained is invalid. Translated by ChatGPT 5