D. Kuroni and the Celebration

Link: D. Kuroni and the Celebration

Description

This is an interactive problem.

After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Kuroni went to an Italian restaurant to celebrate this holy achievement. Unfortunately, the excess sauce disoriented him, and he's now lost!

The United States of America can be modeled as a tree (why though) with n vertices. The tree is rooted at vertex r, wherein lies Kuroni's hotel.

Kuroni has a phone app designed to help him in such emergency cases. To use the app, he has to input two vertices u and v, and it'll return a vertex w, which is the lowest common ancestor of those two vertices.

However, since the phone's battery has been almost drained out from live-streaming Kuroni's celebration party, he could only use the app at most $\lfloor \frac{n}{2} \rfloor$ times. After that, the phone would die and there will be nothing left to help our dear friend! :(

As the night is cold and dark, Kuroni needs to get back, so that he can reunite with his comfy bed and pillow(s). Can you help him figure out his hotel's location?

Interaction
The interaction starts with reading a single integer n ($2 \le n \le 1000$), the number of vertices of the tree.

Then you will read n−1 lines, the i-th of them has two integers xi and yi $\left(1 \leq x_{i}, y_{i} \leq n, x_{i} \neq y_{i}\right)$, denoting there is an edge connecting vertices xi and yi. It is guaranteed that the edges will form a tree.

Then you can make queries of type "? u v" ($1 \le u, v \le n$) to find the lowest common ancestor of vertex u and v.

After the query, read the result w as an integer.

In case your query is invalid or you asked more than $\lfloor \frac{n}{2} \rfloor$ queries, the program will print −1 and will finish interaction. You will receive a Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you find out the vertex r, print "! r" and quit after that. This query does not count towards the $\lfloor \frac{n}{2} \rfloor$ limit.

Note that the tree is fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.

After printing any query do not forget to print end of line and flush the output. Otherwise, you might 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 the documentation for other languages.

Hacks

To hack, use the following format:

The first line should contain two integers n and r $(2 \leq n \leq 1000,1 \leq r \leq n)$, denoting the number of vertices and the vertex with Kuroni's hotel.

The i-th of the next n−1 lines should contain two integers $x_{i}$ and $y_{i}$ ($1 \le x_i, y_i \le n$) — denoting there is an edge connecting vertex $x_{i}$and $y_{i}$.

The edges presented should form a tree.

Example
input
6
1 4
4 2
5 3
6 3
2 3

3

4

4

output

? 5 6

? 3 1

? 1 2

! 4
Note
Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.

The image below demonstrates the tree in the sample test:

Problem solving

这道题的意思就是给你一棵树，让你去找他的根。n为树的节点数，查询次数不能超过$\lfloor \frac{n}{2} \rfloor$ 。每次你可以给出两个点，系统会将这两个点的LCA返回给你，也就是充当下一个输入。这就是交互式的意思。
比如说样例，输入完树之后，你查询了5，6，他们的lca是3，所以你的下一个输入就是3.
假设我们每次都查询两个叶子结点的lca，会有两种情况

1. lca与两个点中的某一个相等，这时这个lca就是我们要找的根节点。
2. lca与这两个点都不相同，这时我们把这两个点删去。

所以我们如果没有找到根节点，那么每次也都可以删除两个点，所以删除$\lfloor \frac{n}{2} \rfloor$ 次之后一定可以找到根节点。

Code

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 1e3 + 10;
vector<int> V[maxn], mid;
int d[maxn], c;
int main()
{
    int t, n;

    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        V[u].pb(v); V[v].pb(u);
        d[v]++, d[u]++; //统计度数用来寻找叶子节点
    }
    t = n >> 1;             //最多n/2次查询
    while (t--) {
        mid.clear();
        for (int i = 1; i <= n; i++) if (d[i] == 1) mid.pb(i);
        int a = mid[0], b = mid[1];
        cout << "? " << a << " " << b << endl;
        cout.flush();
        cin >> c;
        if (c == a || c == b) {
            cout << "! " << c << endl;
            return 0;
        }
        for (auto i:V[a]) d[i]--;
        for (auto i:V[b]) d[i]--;       //与我们将要删除的两个点相连的点的度数全部减一
        d[a] = d[b] = 0;                //要删除的点的度数置为0，就不会再考虑了。
    }
    cout << "! " << c << endl;              //如果查询了n/2次之后还没有遇到lca与叶节点相等的情况，那么此时的lca一定是根节点
    return 0;
}