祝贺我首次切出 2700！祝贺我首次切出 2700！
写个题解纪念。
在这里顺带推销一下我的交互题单。
令两个点分别为 \(x\)，\(y\)，下文所说的“链”的端点为这两个点。
考虑到一开始我们啥也不知道，先整体感知一下，查询一下所有点。那么可以得到链的长度 \(l\) 和链上的一个点 \(u\)。
然后考虑到如果我们已经知道了链的一个端点，直接询问与这个点距离为 \(l\) 的所有点，返回的答案就是另一个点了。所以考虑先把一个端点求出来。
然后就是一些比较智慧的东西了，考虑如下倍增算法：令 \(r=u\)。从大到小遍历所有 \(2\) 的幂。每次查询除了在 \(u\)，\(r\) 路径上的，所有与 \(r\) 距离 \(2^i\) 的点。如果返回的最小值是 \(l\)，那么用返回的点更新 \(r\)。因为这个点一定在链上。倍增完就可以找到一个端点了。
考虑询问次数：\(1+10+1=12\)，倍增是 \(2^9\) 到 \(2^0\)。可以通过 Easy ver，比 Hard ver 只多一次，能不能再给力点呢？
继续压榨现在的算法。如果 \(l < 512\)，倍增就只需要 \(9\) 次了。如果 \(l \ge 512\)，那么肯定 \(l \ge \frac{n}{2}\)。根号分治地，链一定经过重心。然后将 \(u\) 改为树的重心执行上述倍增就行，因为每一个子树不大于 \(\frac{n}{2} \le 500 < 512\)，也可以 \(9\) 次倍增。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 7;
int n, sz[N], mx[N], dep[N], cen, fa[N];
set<int> pth;
vector<int> g[N], tmp;
pair<int, int> Misaka(vector<int> c){cout << "? " << c.size() << " ";for(int x: c) cout << x << " ";cout << endl;int A, B; cin >> A >> B;return {A, B};
}
void addpth(int u, int v){pth.insert(u), pth.insert(v);if(dep[u] < dep[v]) swap(u, v);while(dep[u] > dep[v]){u = fa[u];pth.insert(u);}if(u == v) return;while(u != v){u = fa[u], v = fa[v];pth.insert(u), pth.insert(v);}
}
void find(int u, int pre, int dis, int opt){if(!dis){if((!opt) || (!pth.count(u))) tmp.push_back(u);return;}for(int v: g[u]){if(v != pre) find(v, u, dis - 1, opt);}
}
void get(int u, int pre){dep[u] = dep[pre] + 1;fa[u] = pre;sz[u] = 1, mx[u] = 0;for(int v: g[u]){if(v != pre){get(v, u);mx[u] = max(mx[u], sz[v]);sz[u] += sz[v];}}mx[u] = max(mx[u], n - sz[u]);if(cen == -1 || mx[u] < mx[cen]) cen = u;
}
void solve(){cin >> n;for(int i = 1; i <= n; i ++) g[i].clear();for(int i = 1; i < n; i ++){int u, v; cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}tmp.clear();for(int i = 1; i <= n; i ++) tmp.push_back(i);int cur, len; tie(cur, len) = Misaka(tmp);cen = -1, get(1, 0);if(len >= 512) cur = cen;pth.clear(); pth.insert(cur);for(int i = (1 << 8); i; i >>= 1){tmp.clear(), find(cur, 0, i, 1);if(tmp.empty()) continue;int D, L; tie(D, L) = Misaka(tmp);if(L > len) continue;addpth(cur, D), cur = D;}tmp.clear(), find(cur, 0, len, 0);int ans, tt; tie(ans, tt) = Misaka(tmp);cout << "! " << cur << " " << ans << endl;string res; cin >> res;
}
signed main(){ios::sync_with_stdio(0), cin.tie(0);int t; cin >> t;while(t --) solve();return 0;
}