P14762 [Opoi 2025] CCD’s Song of Everlasting Regret

~~A few days ago~~ One year ago, CCD lost points in a mock contest and got mocked by _Eriri_, so he decided to make a problem to mock _Eriri_ back. > The emperor loved beauty and longed for a lady who could topple a nation, yet after ruling for many years he could not find one. > > In the Jiang family there was a girl just grown up, kept in the inner chambers, unknown to others. > > Born with natural beauty that could not be ignored, one day she was chosen to stand by the ruler. > > Looking back with a smile, a hundred charms appeared; the makeup of the six palaces all lost their color. [upd 2025/5/5].

**Please note: this problem only supports submissions in C++11 or above.** Emperor Dong has a very mysterious rooted tree $T$ with $n$ nodes, with root $1$. And you, as the noble Consort Jiang, really want to know the shape of tree $T$. However, each time you can only ask Emperor Dong one ordered pair $(i,j)\ (1 \le i , j \le n)$, and he will tell you the lowest common ancestor $k$ of these two nodes in the tree. Since Emperor Dong is also busy preparing for Opoi, he only allows you to ask $n \times 300$ questions. Luckily, Emperor Dong likes compact structures, so the number of **leaves of this tree is at most $20$**. This is an interactive problem. When submitting, please add the following function declaration in your program: ```cpp int LCA(int,int); ``` This allows you to call `LCA(x,y)` and get their LCA. You do not need to, and should not, implement the main function. You only need to implement the following function: ```cpp vector guess(int n); ``` - For each test point, the interactive library will call this function only once. - Here, $n$ is the number of nodes of the tree $T$ to be guessed this time. - The returned vector describes the structure of tree $T$. Each `pair` in the `vector` represents an edge $(u,v)$ of the tree. There is no requirement on the order of the two nodes in each edge, nor on the order of the edges. - The time complexity of a single `LCA(x, y)` call is strictly $O(1)$, and the interactive library preprocessing complexity is $O(n \log_2 n)$. - **The SPJ will not return `WA` because you called LCA too many times, but if you exceed $n \times 300$ calls, then all subsequent LCA call results will be `-1`.** There is a sample template `template.cpp` in the attachments. Using it, you can get a good score of $0$ points.

N/A

# Hint ### Sample Explanation | You | Interactor | | :----------: | :----------: | | `LCA(1,2)` | `1` | | `1 2` | Accepted | Besides the sample output, outputting `2 1` is also a valid solution. --- ### Constraints and Conventions For $100\%$ of the testdata, $1 \le n \le 2 \times 10^4$. **Partial score: there are $20$ groups of testdata in total. For the $i$-th group, it is guaranteed that the number of leaves of the tree is at most $i$.** --- ##

### Sample Explanation | You | Interactor | | :----------: | :----------: | | `LCA(1,2)` | `1` | | `1 2` | Accepted | Besides the sample output, outputting `2 1` is also a valid solution. --- ### Constraints and Conventions For $100\%$ of the testdata, $1 \le n \le 2 \times 10^4$. **Partial score: there are $20$ groups of testdata in total. For the $i$-th group, it is guaranteed that the number of leaves of the tree is at most $i$.** --- ### Hint If you do not know how to solve interactive problems, you can refer to [this problem](P1947). The template program and the template interactive library for this problem can be found in the attachments: `template.cpp` and `s_interactor.cpp`. Translated by ChatGPT 5