This is an interactive problem.
Description
You are given a tree with $n$ nodes, but you do not know its structure. You have an initially empty set of nodes $S$. You can perform the following two operations:
- Add a node to $S$.
- Remove a node from $S$.
After each operation, the interactor will return the size of the largest connected component of the subgraph induced by $S$ (i.e., the graph containing only the nodes in $S$ and the edges whose both endpoints are in $S$).
You need to reconstruct the structure of the tree using as few operations as possible.
Implementation Details
Ensure your program starts with #include "wheretoreach.h". You do not need to, and should not, implement the main function. You must implement the following function:
void solve (int n);- Here, $n$ represents the number of nodes in the tree, with nodes numbered from $1$ to $n$.
You can call the following functions provided by the interactor:
int add (int x);
int remove (int x);
void report (int x, int y);add(x)is used to add a node $x$ to $S$. If $x$ is already in $S$, nothing happens.- You must ensure $1 \le x \le n$.
- This function returns the size of the largest connected component of the induced subgraph of $S$ after the operation.
remove(x)is used to remove a node $x$ from $S$. If $x$ is not in $S$, nothing happens.- You must ensure $1 \le x \le n$.
- This function returns the size of the largest connected component of the induced subgraph of $S$ after the operation.
report(x, y)indicates that you have found an edge $(x, y)$ in the tree.- You must call this function exactly $n - 1$ times to submit all edges of the tree. The order and orientation of the edges are arbitrary.
The total number of calls to add and remove must not exceed $2 \times 10^6$.
It is guaranteed that under the given constraints and conditions, the execution time of the interactor in the final test will not exceed $2000\text{ ms}$, and the memory usage will not exceed $128\text{ MiB}$.
The interactor is not adaptive, meaning the tree structure is fixed and will not change during the interaction process.
Testing Your Program
The file implementer.cpp in the problem directory is our provided reference implementation of the interactor. The final testing interactor may differ from the sample interactor, so your implementation should not rely on the specific implementation of the sample interactor.
You need to compile your program using the following command in the problem directory:
g++ implementer.cpp sample.cpp -o sample -O2 --std=c++14 -lm
For the resulting executable:
The executable will read the following data from standard input:
The first line contains an integer $n$, representing the number of nodes in the tree. You must ensure $1 \le n \le 10^4$.
The next $n - 1$ lines each contain two integers $x, y$, describing an edge in the tree. The order and orientation of the edges are arbitrary.
After reading the input, the interactor will call the solve function.
If your implementation does not meet the requirements in the "Implementation Details" section, the interactor will output a single -1 to standard output. Specifically, the interactor will output -1 if:
An $x$ that does not satisfy $1 \le x \le n$ is passed to add or remove;
The total number of calls to add and remove exceeds $2 \times 10^6$;
The number of report function calls is not $n - 1$ when the solve function terminates.
Otherwise, the interactor will output the following to standard output:
The first line contains two integers $Q, c$, where $Q$ is the total number of calls to add and remove, and $c = 1$ indicates your answer is correct, while $c = 0$ indicates it is incorrect.
* The following lines contain the record of your calls to add, remove, and report. You can refer to Example 1 for the format.
Examples
Input 1
3 1 2 2 3
Output 1
4 1 add(2); add(3); add(1); remove(2); report(3,2); report(1,2);
Note
The example output shows the output of the sample program for this set of examples.
Subtasks
For all test cases, $1 \le n \le 10^4$.
- Subtask 1 (10%): $n = 500$.
- Subtask 2 (20%): $n = 2500$.
- Subtask 3 (70%): $n = 10^4$.
Scoring
This problem is subject to the same constraints as traditional problems; for example, compilation errors will result in 0 points for the entire problem, and runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test cases. You may only access variables or memory defined by yourself or provided by the interactor. Attempting to access other memory locations may result in compilation or runtime errors.
For test cases in Subtask 1 and 2, as long as your interaction follows the rules in "Implementation Details" and provides the correct answer, you will receive full marks.
For test cases in Subtask 3, assuming your interaction follows the rules in "Implementation Details" and provides the correct answer, let $Q$ be the total number of calls to add and remove. Your score is $f(Q)$, where:
$$ f(Q) = \begin{cases} 70 & (0.0 \times 10^6 \le Q \le 0.6 \times 10^6) \\ 70 - \frac{Q - 0.6 \times 10^6}{5000} & (0.6 \times 10^6 < Q \le 0.7 \times 10^6) \\ 50 - \frac{Q - 0.7 \times 10^6}{15000} & (0.7 \times 10^6 < Q \le 1.0 \times 10^6) \\ 30 - \frac{Q - 1.0 \times 10^6}{25000} & (1.0 \times 10^6 < Q \le 1.5 \times 10^6) \\ 10 - \frac{Q - 1.5 \times 10^6}{50000} & (1.5 \times 10^6 < Q \le 2.0 \times 10^6) \end{cases} $$
This is a continuous piecewise linear function. You can understand it as: your first $0.6 \times 10^6$ calls are free; for the subsequent $0.1 \times 10^6$ calls, you lose 1 point for every 5000 calls; for the subsequent $0.3 \times 10^6$ calls, you lose 1 point for every 15000 calls; for the subsequent $0.5 \times 10^6$ calls, you lose 1 point for every 25000 calls; for the subsequent $0.5 \times 10^6$ calls, you lose 1 point for every 50000 calls.
Your score for each subtask is the minimum score obtained among all test cases within that subtask.
You must not attempt to obtain internal information about the interactor through illegal means, such as attempting to interact with standard input/output streams. Such behavior will be considered cheating.