每次询问两个点的 LCA，最多询问 $\lfloor \frac{n}{2} \rfloor$ 次确定根。
很傻的一道交互题。
注意到如果一个叶子和另一个点的 LCA 就是这个叶子，那么这个叶子一定为根；如果不是，则这个叶子一定不是根。
那么我们每次询问两个叶子的 LCA 即可，如果是其中某一个点，则那个点就是根；否则删掉两个点，注意可能产生新的叶子。
最坏情况下，每次询问会删掉两个叶子，那么 $\lfloor \frac{n}{2} \rfloor$ 次后最多只剩下一个点，这个点显然就是根了。
```cpp
const int N = 1e3 + 7;
int n, d[N], v[N];
vi e[N];
int main() {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1, x, y; i < n; i++)
cin >> x >> y, e[x].pb(y), e[y].pb(x), d[x]++, d[y]++;
queue<int> q;
for (int i = 1; i <= n; i++)
if (d[i] == 1) q.push(i);
for (int i = 1; i <= n / 2; i++) {
int x = q.front();
q.pop();
int y = q.front();
q.pop();
cout << "? " << x << " " << y << endl;
fflush(stdout);
int z;
cin >> z;
if (z == x || z == y) {
cout << "! " << z << endl;
return 0;
}
for (int z : e[x])
if (!v[z] && (--d[z] == 1)) q.push(z);
for (int z : e[y])
if (!v[z] && (--d[z] == 1)) q.push(z);
v[x] = v[y] = 1;
}
for (int i = 1; i <= n; i++)
if (!v[i]) cout << "! " << i << endl;
return 0;
}
```