P17271 [eJOI 2026] Reconstruct

*This is an interactive problem.* Bissy is about to enter the volunteer-organized orienteering game *Final destination*, where EJOI delegations compete to visit locations across the city. She is more interested in how the game was designed than in winning it. There are $N$ locations and $N$ teams. Every team must visit all locations, and the teams have distinct starting locations: team $i$ starts from location $i$. Each team receives its own route. The routes are based on a hidden structure of fast public transport lines. The jury chose $N-1$ lines, each connecting two locations, so that every location is reachable from every other location. This structure is a tree. For every starting location $i$, the jury generated an arbitrary DFS walk and assigned it as team $i$'s route. Bissy wants to discover the hidden tree. She may ask questions of the form: > What is the $j$-th destination of team $i$? Write `find_tree` to find the hidden tree. A **DFS walk** of a tree is the order in which its vertices are first visited by depth-first search. Starting at a vertex $v$, the procedure repeatedly moves recursively to an unvisited neighbor. When none remains, it returns to the previously visited vertex and continues. :::align{center}  ::: In the figure, $v=4$ and the arrows show the steps of a DFS. The generated walk is $[4,1,2,0,3,6,7,5]$. The order in which neighbors are visited matters; another possible walk is $[4,3,5,7,6,1,0,2]$. The tree and all $N$ DFS walks are fixed before your program starts and do not change in response to your questions. Different DFS walks may use different neighbor orders. ### Implementation details Implement: ```cpp std::vector find_tree(int N) ``` - $N$: the number of locations; - return value: a list of $N-1$ tree edges. The order of the edges and the order of their endpoints do not matter. For each test, this function may be called up to $T$ times. To interact with the jury, call: ```cpp int guess(int i, int j) ``` It returns the $j$-th location in the DFS walk starting at $i$. In particular, `guess(i, 0)` returns $i$. The function responds in constant time $O(1)$ for subtasks $0$ through $6$, and in logarithmic time $O(\log N)$ for subtask $7$. You must have $0\le i,j\le N-1$; otherwise, your solution receives `Output isn't correct: Invalid call`.

Two sample graders are provided. For local testing, `Lgrader.cpp` can be compiled with your program. It reads the number $T$ of test cases. For every case, it reads $N$, then $N-1$ lines of edges, then $N$ lines of $N$ integers describing the DFS walks. Walk $i$ must start at vertex $i$. Set `AUTO_GENERATE` to `true` to let the grader generate the walks. The grader reports an error if the result is incorrect; otherwise, it reports the number of queries for every test case and the overall maximum. This grader does not support sufficiently large $N$, namely the constraints of subtask $7$. For system user tests, `stub.cpp` can be used with your program. Its input format is the same, but it has no built-in walk generation.

N/A

### Example Assume the hidden public transport tree is: :::align{center}  ::: For starting location $0$, suppose the walk is $[0,1,2,4,3,5]$. One possible interaction is: | Participant program | Jury program | |---|---| | | `find_tree(6)` | | `guess(0, 0)` | returns `0` | | `guess(0, 1)` | returns `1` | | `guess(0, 2)` | returns `2` | | `guess(0, 3)` | returns `4` | | `guess(0, 4)` | returns `3` | | `guess(0, 5)` | returns `5` | | `return {{0,1},{0,2},{4,0},{5,4},{3,4}};` | | The queries do not uniquely determine the tree, but this is the answer to the test in subtask $0$. ### Constraints - $2\le N\le 2^{16}+1$ - Let $N_{\max}$ be the maximum $N$ among calls in one test: - if $N_{\max}\le 9$, then $1\le T\le 100$; - if $N_{\max}\le 2^{10}+1$, then $1\le T\le 10$; - if $N_{\max}\le 2^{16}+1$, then $1\le T\le 3$. - The system grader may use up to 280 MiB, which counts toward your solution's memory. ### Subtasks | Subtask | Points | $N$ | Additional constraints | |:--:|:--:|:--:|---| | 0 | 0 | - | The example. | | 1 | 11 | $\le 9$ | - | | 2 | 6 | $\le 100$ | Every vertex is connected to at most two others. | | 3 | 13 | $\le 100$ | Every walk is generated by a DFS that always prioritizes moving away from vertex $0$. If several such moves are possible, one is chosen arbitrarily. | | 4 | 11 | $\le 100$ | Every vertex other than $0$ is connected to at most two others. | | 5 | 10 | $\le 100$ | - | | 6 | 31 | $\le 2^{10}+1$ | - | | 7 | 18 | $\le 2^{16}+1$ | - | ### Scoring For subtasks $0$ through $5$, you receive full points if you find the tree within the time limit. For subtasks $6$ and $7$, let $Q_{\max}$ be the maximum number of queries used on one subtest. The score fraction $S$ for a test is: - if $Q_{\max}\le L_1$, then $S=1.0$; - if $L_1