Finding the Vertex
Contest: Codeforces Round 680 (Div. 1, based on Moscow Team Olympiad)
Difficulty rating: 3500
Tags: brute force, dfs and similar, dp, interactive, trees

This is an interactive problem.

You are given a tree — connected undirected graph without cycles. One vertex of the tree is special, and you have to find which one. You can ask questions in the following form: given an edge of the tree, which endpoint is closer to the special vertex, meaning which endpoint's shortest path to the special vertex contains fewer edges. You have to find the special vertex by asking the minimum number of questions in the worst case for a given tree.

Please note that the special vertex might not be fixed by the interactor in advance: it might change the vertex to any other one, with the requirement of being consistent with the previously given answers.

Input format:
You are given an integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of vertices in a tree.

The folloiwing $$$n-1$$$ lines contain two integers each, $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), that denote an edge in the tree connecting $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

Interaction format:
After reading the input data, one can start making queries. There are two possible queries:

1. "? $$$u$$$ $$$v$$$" — to ask for an edge $$$(u, v)$$$ ($$$1 \le u, v \le n$$$) which of the endpoints is closer to the special vertex. The answer to this query is one of the endpoints. Note that, $$$u$$$ and $$$v$$$ must be connected by an edge, and hence they can not have the same distance to the special vertex.
2. "! $$$u$$$" — to indicate that you found the special vertex. After the program does that, it must immediately terminate.

Do not forget to output the end of line and flush the output. Otherwise you will get Idleness limit exceeded verdict. To flush the output, you can use:

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

In case you ask more queries than needed in the worst case for a given tree, you will get verdict Wrong answer.

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

Note:
Hacks are forbidden in this task.

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

Example output:
? 3 4
? 2 3
? 1 2
! 1

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

Example output:
? 1 2
? 1 3
? 1 4
! 4

Editorial:
Consider the optimal strategy.
Some edge will be your first query, mark it with a number $$$0$$$.
After that, build similar colourings (recursively) for components on both sides of the edge, but increase their weights by one (to have only one zero in total).
This colouring corresponds to the strategy, and if $$$k$$$ is the maximum weight of an edge in it, then this strategy can find a vertex in $$$k+1$$$ queries in the worst case.
This colouring has a wonderful property that helps us identify the vertex: on a path between any two edges with the same colour an edge with the smaller colour presents.
And any colouring with this property corresponds to a proper strategy! (Each time you can ask an edge with the smallest weight in the current component)
To make it easier for us, "invert" all weights in the colouring, mark the first edge with the weight $$$k-1$$$, and then use the same construction as we had before for our colouring, but now subtract $$$1$$$ from the edges (weights should remain non-negative).
Now our goal is to find colouring with the min weight of the max edge, such that each pair of edges with the same colours have an edge with the larger colour between them.
We will build this colouring using subtree DP.
For the fixed colouring of a subtree of the vertex $$$v$$$, let's see which colours are visibile if you will look from $$$v$$$ towards the subtree.
The colour is visible, if there is such an edge of this colour, that there are no edges with the larger colour on a path from this edge to $$$v$$$.
Potential function of our colouring is the sum $$$2^{c_1} + 2^{c_2} + \ldots + 2^{c_k}$$$, where $$$c_i$$$ are visible colours. Note that this value is a long number! Because our answer can be large.
Lemma: we are interested only in the colouring of our subtree with the smallest potential.
Assume that all subtrees of vertex $$$v$$$ are already coloured into colourings with the smallest potentials.
Then we have to choose some weights of edges outgoing from $$$v$$$, such that after adding these edges to $$$v$$$, different subtrees won't have common visible colours (otherwise you will get a bad pair of edges of the same colour).
You can color an edge from vertex $$$v$$$ to its child $$$u$$$ in a colour $$$c$$$, if a colour $$$c$$$ is not visible from $$$u$$$. After that, all weights smaller than $$$c$$$ will disappear from the set of visible colours, but the colour $$$c$$$ will be added.
You have to change colourings of the subtrees in this way, to not have carries during the addition of the potentials (it will correspond to the situation without common visible colours). Under this constraint, we have to minimize the total sum, the potential of $$$v$$$.
From this setting, the proof of the previous lemma is clear: for larger values of the potential, possible choices are not better.
You have to solve a problem: you are given an array $$$a_1, a_2, \ldots, a_k$$$ of long binary numbers. You have to find an array with the smallest sum $$$b_1, b_2, \ldots, b_k$$$, such that $$$b_i > a_i$$$, and no carries will happen during the addition $$$b_1 + b_2 + \ldots + b_k$$$.
You can solve this problem with a quite simple greedy algorithm: we will set bits greedily from left to right, and check that we can finish our goal with the fixed prefix. To check that you can get some answer with the fixed prefix of bits and the upper bound on the used bits, you can go from left to right and each time when you have to replace some number to the current bit, replace the number with the largest suffix. You can implement it in a naive way in $$$\mathcal{O}{(n^3)}$$$, but it also can be implemented in $$$\mathcal{O}{(n \log n)}$$$.
You have to solve this subtask $$$n$$$ times, and we will get the solution with complexity $$$\mathcal{O}{(n \cdot T(n))} = \mathcal{O}{(n^2 \log n \ldots n^4)}$$$.