Lost Nodes
Contest: Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: constructive algorithms, dp, graphs, interactive, sortings, trees

This is an interactive problem.

As he qualified for IOI this year, Little Ericyi was given a gift from all his friends: a tree of $$$n$$$ nodes!

On the flight to IOI Little Ericyi was very bored, so he decided to play a game with Little Yvonne with his new tree. First, Little Yvonne selects two (not necessarily different) nodes $$$a$$$ and $$$b$$$ on the tree (without telling Ericyi), and then gives him a hint $$$f$$$ (which is some node on the path from $$$a$$$ to $$$b$$$).

Then, Little Ericyi is able to ask the following question repeatedly:

- If I rooted the tree at node $$$r$$$ (Ericyi gets to choose $$$r$$$), what would be the Lowest Common Ancestor of $$$a$$$ and $$$b$$$?

Little Ericyi's goal is to find the nodes $$$a$$$ and $$$b$$$, and report them to Little Yvonne.

However, Little Yvonne thought this game was too easy, so before he gives the hint $$$f$$$ to Little Ericyi, he also wants him to first find the maximum number of queries required to determine $$$a$$$ and $$$b$$$ over all possibilities of $$$a$$$, $$$b$$$, and $$$f$$$ assuming Little Ericyi plays optimally. Little Ericyi defines an optimal strategy as one that makes the minimum number of queries. Of course, once Little Ericyi replies with the maximum number of queries, Little Yvonne will only let him use that many queries in the game.

The tree, $$$a$$$, $$$b$$$, and $$$f$$$ are all fixed before the start of the game and do not change as queries are made.

Interaction format:
First read a line containing the integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of nodes in the tree.

The next $$$n−1$$$ lines describe Little Ericyi's tree. These lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) denoting an edge between $$$u$$$ and $$$v$$$ ($$$u \neq v$$$). It is guaranteed that these edges form a tree.

After that you should output $$$k$$$, the maximum number of queries needed to determine $$$a$$$ and $$$b$$$ over all possibilities of $$$a$$$, $$$b$$$, and $$$f$$$ assuming Little Ericyi plays optimally. You should output end of line and flush the output after printing $$$k$$$.

After that read a line containing the integer $$$f$$$ ($$$1 \le f \le n$$$) — the hint: a node on the path from $$$a$$$ to $$$b$$$, inclusive.

After that, you can start making queries. You will be limited to making at most $$$k$$$ queries, where $$$k$$$ is the number you printed.

Each query is made in the format "? r", where $$$r$$$ is an integer $$$1 \le r \le n$$$ denoting the root node you want for the query.

You will then receive an integer $$$x$$$ ($$$1 \le x \le n$$$), the Lowest Common Ancestor of $$$a$$$ and $$$b$$$ if the tree was rooted at $$$r$$$.

When your program has found the nodes $$$a$$$, $$$b$$$, report the answer in the following format: "! a b", where $$$a$$$ and $$$b$$$ are the two hidden nodes and terminate your program normally immediately after flushing the output stream. You may output $$$a$$$ and $$$b$$$ in any order.

After printing a query do not forget to output end of 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.

If at any point you make an invalid output or make more than $$$k$$$ queries, the interaction will terminate and you will receive a Wrong Answer verdict. An invalid output is defined as either an invalid query or a value of $$$k$$$ less than $$$0$$$ or greater than $$$n$$$.

Hacks

To hack a solution, use the following format:

The first line contains the integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The next $$$n−1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) denoting an edge between $$$u$$$ and $$$v$$$ ($$$u \neq v$$$). These $$$n-1$$$ edges must form a tree.

The next line of input contains the nodes $$$a$$$ and $$$b$$$ ($$$1 \le a,b \le n$$$), separated by a space.

The final line of input contains the integer $$$f$$$ ($$$1 \le f \le n$$$). Node $$$f$$$ should be on the simple path from $$$a$$$ to $$$b$$$ (inclusive).

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

Note:
Here is the the tree from the first sample interaction. Nodes $$$a$$$ and $$$b$$$ are highlighted.

Notice that $$$a$$$ and $$$b$$$ can be output in any order.

Additionally, here are the answers to querying every single node $$$1,2,\ldots,n$$$ for your convenience:

- $$$1$$$: $$$1$$$
- $$$2$$$: $$$2$$$
- $$$3$$$: $$$2$$$
- $$$4$$$: $$$4$$$

__________________________________________

Here is the the tree from the second sample interaction. Again, nodes $$$a$$$ and $$$b$$$ are highlighted.

Lastly, here are the answers to querying every single node $$$1,2,\ldots,n$$$ (in example $$$2$$$) for your convenience:

- $$$1$$$: $$$1$$$
- $$$2$$$: $$$4$$$
- $$$3$$$: $$$1$$$
- $$$4$$$: $$$4$$$
- $$$5$$$: $$$4$$$

Example input:
4
3 2
2 1
2 4

1

1

2

2

Example output:
3

? 1

? 2

? 3

! 4 1

Example input:
5
3 1
1 4
4 5
4 2

1

4

1

4

Example output:
3

? 4

? 1

? 5

! 1 4

Editorial:
Finding the theoretical maximum
For now, let's only look at finding $$$k$$$ for fixed $$$f$$$. We will expand for all $$$f$$$ later.
We know that $$$f$$$ is on the path from $$$a$$$ to $$$b$$$. Let us root the tree at $$$f$$$. Thus, we know that the path will pass through the root, and that there are exactly $$$2$$$ non-negative length chains beginning at the root. With that in mind, let's take a look at what a question "? r really does.
• What happens if $$$r$$$ is on the path from $$$a$$$ to $$$b$$$? In this case, we obtain $$$r$$$ as the answer.
• What happens if $$$r$$$ is not on the path from $$$a$$$ to $$$b$$$? In this case, we obtain the closest node to $$$r$$$ on the path from $$$a$$$ to $$$b$$$.
Let's try to find one endpoint of one of these chains first. Consider the following dynamic programming structure:
• Let $$$dp[u]$$$ denote the minimum number of questions required to "solve" the subtree rooted at $$$u$$$. By "solve", we mean to determine if the endpoint of a chain is in the subtree or not, and if it is in the subtree, the exact node.
The base case is pretty obvious. For a leaf node, it will take exactly $$$1$$$ question to solve a leaf node. If the endpoint of the chain does indeed end at the leaf node, then a question will return the leaf node. Otherwise it'll return an ancestor of the leaf.
Let's move on to a non-base case at a node $$$x$$$. Let's call the most "expensive" child of $$$x$$$ as the child $$$c$$$ with the largest $$$dp[c]$$$ (i.e. takes the most number of questions to "solve").
For now, assume we know that an endpoint exists in the subtree rooted at $$$x$$$, and is not $$$x$$$. Thus, we will need to iterate through each child to determine in which child's subtree the endpoint exists. We will need to use one question per child. However, note that not all of these questions count towards our question count. There are two cases:
1. In the current child we are exploring, the endpoint does exist there. In this case, the question we used does not count towards our question count. We can use a question from the child's question count. This may seem a bit strange, but if we query correctly, then in the same time we check if the endpoint exists in the child's subtree, we also process the most "expensive" child of the child and determine if the endpoint exist in that child of the child's subtree.
2. In the current child we are exploring, the endpoint doesn't exist there. In this case, the question we used must count towards our question count. We could consider this a "wasted" question as we didn't learn anything new about where the endpoint is, just that it's not in this child.
Now, in which order should be explore the children? We can greedy this. Recall that any "wasted" questions count towards our question count. Thus, for more "expensive" children, we want to have wasted less questions when we get to the child, as in the case the endpoint does exist there, we would need even more questions (adding the "wasted" questions to $$$dp[c]$$$ where $$$c$$$ is the child). This gives us the following idea:
• To determine if the $$$i^\text{th}$$$ ($$$0$$$-indexed) child $$$c$$$ of $$$x$$$ contains the endpoint, we would need to waste $$$i$$$ questions. If the endpoint does exist in $$$c$$$, we would need to use a total of $$$dp[c] + i$$$ questions to "solve" the subtree rooted at $$$x$$$. Since we are trying to find the worst case, we want to order the children of $$$x$$$ such as to minimize the maximum of all $$$dp[c] + i$$$. The optimal ordering is the non-increasing order of $$$dp[c]$$$.
The transition is thus:
$$$dp[x] = \max\{dp[c_i] + i\} \,\, \forall \,\, 0 \le i < |c|$$$, where the $$$dp$$$ values are sorted in non-increasing order, and $$$c$$$ are the children of $$$x$$$.
Now wait! We haven't handled the case where the endpoint doesn't exist in $$$x$$$ or the case where the endpoint is $$$x$$$ yet! Turns out, both of these cases are already handled for us. We only need to be a bit careful when we actually perform the interaction later on.
• If the endpoint doesn't exist in $$$x$$$, we would have already realized when one of the questions to a child of $$$x$$$ returns an ancestor of $$$x$$$. This question count won't be lost though. It will simply be counted towards a "wasted" question for one of the ancestors of $$$x$$$.
• If the endpoint is $$$x$$$, then all of the questions to a child of $$$x$$$ will return $$$x$$$ (not a ancestor of $$$x$$$). Thus, we will know that the endpoint is $$$x$$$ with exactly $$$|c|$$$ wasted questions. Notice, however, that $$$|c| \le dp[x]$$$ by the nature of the transition. Thus, this case will never be our worst case, so we can ignore it for the dynamic programming.
We now have the dynamic programming complete, but notice that it's only for the endpoint of one chain. At our root $$$f$$$, there are two chains with two endpoints. Thus, our final answer won't be simply taking $$$dp[f]$$$. It will require a bit more computation.
For now, assume that both endpoints are not $$$f$$$ (i.e. both chains have positive length). Following a similar analysis as the dynamic programming transition, we have that for any child that does not contain either chain endpoint, we would need to "waste" a question. Once again, the optimal ordering is to process in non-increasing order. However, adding $$$i$$$ to the $$$i^\text{th}$$$ child is no longer correct. Consider the following observations:
1. When processing a child that doesn't contain a chain, that child only takes one question to determine that both chains are not in that child.
2. For the first child that we know contains a chain, we don't "waste" a question. This question is included in that child's question count.
With observation $$$1$$$, we are basically figuring out the first chain's endpoint for free. There are no wasted questions, as all wasted questions will be counted for the second chain. With observation $$$2$$$, we have that adding $$$i$$$ wasted questions is no longer correct. We only waste $$$i - 1$$$ questions for the $$$i^\text{th}$$$ child, as one of the processed children contains the first chain (and thus doesn't waste a question).
Thus, for the root, our formula is:
$$$ans = \max\{dp[c_j] + dp[c_i] + i - 1\} \,\, \forall \,\, 0 \le j < i < |c|$$$, where the $$$dp$$$ values are sorted in non-increasing order, and $$$c$$$ is the children of $$$f$$$. Note that this formula has an $$$\mathcal{O}(n^2)$$$ worst case for a star graph, so we will need to optimize it.
Our optimized formula is:
$$$ans = dp[c_0] + \max\{dp[c_i] + i - 1\} \,\, \forall \,\, 1 \le i < |c|$$$, where the $$$dp$$$ values are sorted in non-increasing order, and $$$c$$$ is the children of $$$f$$$.
Once again, with a similar analysis as what was done for the $$$dp$$$ computation, the case that one (or both) chains have a zero length will never be the worst case, and so we can ignore it for the dynamic programming. However, the case must still be handled during interaction.
Recall that the above was for a fixed $$$f$$$. To find the maximum for all $$$f$$$, we can perform a tree walk. When transitioning from one root to an adjacent root, use a prefix and suffix max array to compute $$$\max{dp[c_i] + i}$$$, ignoring the $$$c_i$$$ that is the new root. Both max arrays should store $$$dp[c_i] + i$$$, not $$$dp[c_i]$$$. Remember to subtract $$$1$$$ from the suffix array values, as there is one less wasted question.
——————————————————
Interacting
If you understood the initial dynamic programming computation for determining the theoretical maximum, the interaction should be relatively straightforward, and so we will leave it as an exercise for the reader. Be careful when handling the special cases that were ignored during the dynamic programming.
——————————————————
The final time complexity is $$$\mathcal{O}(n \log n)$$$ and memory complexity is $$$\mathcal{O}(n)$$$.