Centroid Guess
Contest: Pinely Round 1 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: interactive, probabilities, trees

This in an interactive problem.

There is an unknown tree consisting of $$$n$$$ nodes, which has exactly one centroid. You only know $$$n$$$ at first, and your task is to find the centroid of the tree.

You can ask the distance between any two vertices for at most $$$2\cdot10^5$$$ times.

Note that the interactor is not adaptive. That is, the tree is fixed in each test beforehand and does not depend on your queries.

A vertex is called a centroid if its removal splits the tree into subtrees with at most $$$\lfloor\frac{n}{2}\rfloor$$$ vertices each.

Input format:
The only line of the input contains an integer $$$n$$$ ($$$3\le n\le 7.5\cdot10^4$$$) — the number of nodes in the tree.

Interaction format:
Start interaction by reading $$$n$$$.

To ask a query about the distance between two nodes $$$u, v$$$ ($$$1 \le u, v \le n$$$), output "? u v".

If you determine that the centroid of the tree is $$$x$$$, use "! x" to report.

After printing a query, do not forget to output the end of a line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hacks are disabled in this problem.

It's guaranteed that there are at most $$$500$$$ tests in this problem.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
Here is an image of the tree from the sample.

Example input:
5

2

1

2

3

1

1

1

Example output:
? 1 2

? 1 3

? 1 4

? 1 5

? 2 3

? 3 4

? 4 5

! 3

Editorial:
Assuming we have already determined that the centroid of the tree is located on the path between $$$u$$$ and $$$v$$$, we may now consider how to locate it.
Let $$$c_1,c_2,\dots,c_k$$$ be the vertices on the path from $$$u$$$ to $$$v$$$. Let $$$A_i$$$ be the set of vertices reachable from $$$c_i$$$ (including $$$c_i$$$) if we erase all other vertices on the path from $$$u$$$ to $$$v$$$. Then we may find that $$$A_1,A_2,\dots,A_k$$$ are a division of all vertices.
Let $$$s_i$$$ be the size of $$$A_i$$$. Then there must exist a vertex $$$c_x$$$ on the path satisfying that $$$\max\{\sum_{i=1}^{x-1}s_i,\sum_{i=x+1}^ks_i\}\leq \lfloor\frac n2\rfloor$$$. Notice that the vertices that do not satisfy the condition could not be a centroid, and it is already determined that the centroid is on the path, so $$$c_x$$$ is exactly the centroid of the tree.
Then we may consider finding out which set each vertex belongs to with $$$2n$$$ queries so that we can calculate the value of $$$s_i$$$. For each vertex $$$x$$$, we may query $$$dis_{u,x}$$$ and $$$dis_{v,x}$$$. For any two vertices $$$x$$$ and $$$y$$$ that belong to the same set, $$$dis_{u,x}-dist_{v,x}$$$ should be equal to $$$dis_{u,y}-dis_{v,y}$$$. Let $$$t_1=dis_{u,x}-dis_{v,x}$$$ and $$$t_2=dis_{u,v}$$$, then $$$x\in A_{(t_1+t_2)/2+1}$$$. Thus we have found out the sets each vertex belongs to, as well as the value of $$$s_i$$$, as well as the centroid. This process requires at most $$$7.5\times10^4\times2=1.5\times 10^5$$$ queries.
Now the problem remains to find a pair of vertices $$$u$$$ and $$$v$$$ such that the centroid locates on the path from $$$u$$$ to $$$v$$$.
We can pick a constant $$$M$$$ satisfying that $$$\frac{M(M-1)}2\leq 5\times 10^4$$$, then select $$$M$$$ vertices on the tree randomly, and query the distances between every pair of selected vertices. This requires $$$\frac{M(M-1)}2\leq 5\times 10^4$$$ queries.
Let these $$$M$$$ vertices be $$$p_1,p_2,\dots,p_M$$$. We can build a virtual tree with $$$p_1$$$ being the root that contains all the LCAs of each pair of vertices. Observe that $$$dis_{x,y}+dis_{y,z}=dis_{x,z}$$$ if and only if $$$y$$$ is located on the path between $$$x$$$ and $$$z$$$. For a vertex $$$p_x$$$, we can find out all vertices on the path from $$$p_1$$$ to $$$p_x$$$, and then find out the closest vertex to $$$p_x$$$ and connect them. It is exactly the deepest ancestor of $$$p_x$$$.
Now that we have constructed the virtual tree without the LCAs with $$$p_1$$$ being the root, we will then add the LCAs into the virtual tree.
Start DFS from $$$p_1$$$. Assume the current vertex is $$$u$$$. Enumerate through the nodes adjacent to $$$u$$$. Assume the current vertex is $$$v$$$. If there exists another vertex $$$x$$$ which is adjacent to $$$u$$$ satisfying that $$$u$$$ is not on the path between $$$x$$$ and $$$v$$$, then $$$x$$$ and $$$u$$$ should be both in the subtree of one of $$$u$$$'s child nodes. After finding out all vertices that are in the same subtree as $$$v$$$, it would be easy to calculate the depth of their LCAs as well as the distance between an LCA vertex and all other vertices in the virtual tree. Then, remove the old edge, and then add edges between the LCA and all vertices found in the same subtree as $$$v$$$. Lastly, add an edge between the LCA and $$$u$$$. Then repeat the process above, until any two vertices adjacent to $$$u$$$ are not in the same subtree of a child node of $$$u$$$. Then DFS the child nodes of $$$u$$$. We will get the whole virtual tree after all DFS are done.
For the $$$M$$$ vertices chosen from the beginning, we assume that their weights are all $$$1$$$, while other vertices have $$$0$$$ weight. Then we may find the weighted centroid of the virtual tree (when there are multiple such centroids, arbitrarily pick one), and then make it the root. Then for the two vertices with the largest and second-largest subtree of the root, DFS them, recursively find their child vertex with the largest subtree. We will be resulted with $$$2$$$ leaf nodes. Then the centroid of the hidden tree is highly possible to be located on the path between these $$$2$$$ nodes. The number of queries in both parts would not exceed $$$2\times 10^5$$$.
Proof of correctness:
If the centroid is not on the path between $$$u$$$ and $$$v$$$, assume the centroid of the virtual tree is in the subtree $$$E$$$ of the centroid of the hidden tree. If the subtrees other than $$$E$$$ contain at least $$$\frac 13$$$ of the $$$M$$$ vertices, then the centroid of the hidden tree must be on the path between $$$u$$$ and $$$v$$$. So there will be at most $$$\frac 13$$$ of the $$$M$$$ vertices not being in $$$E$$$. In other words, for each of $$$M$$$ vertices, it has a possibility greater than $$$\frac 12$$$ of not being in $$$E$$$, and there will be at most $$$\frac 13$$$ of the vertices which are not in $$$E$$$. The possibility of the algorithm being wrong is not greater than $$$\sum_{i=0}^{M/3}C_M^i/2^M$$$, let $$$M=316$$$, then the value would be approximately $$$6\times 10^{-10}$$$.