交互题,给出树的连接方式,找出最大边权对应两个端点。
输入查询集合,返回 m a x ( d i s t ( u , v ) ) max(dist(u,v)) max(dist(u,v))。
欧拉序得出的序列中,相邻元素之间存在一条边,直接二分即可。
vec<int> G[N], s; void dfs(int u, int fa) { for (int v : G[u]) { if (v == fa) continue; s.pb(v), dfs(v, u), s.pb(u); } } int query(int l, int r) { vec<int> tmp; for (int i = l ; i <= r; i++) tmp.pb(s[i]); sort(all(tmp)); tmp.erase(unique(all(tmp)), tmp.end()); cout << "? " << tmp.size() << ' '; for (int x : tmp) cout << x << ' '; cout << '\n'; // cout.flush(); int res; cin >> res; return res; } int main() { int n; cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; G[u].pb(v), G[v].pb(u); } s.pb(1), dfs(1, 0); int l = 0, r = s.size() - 1; int ans = query(l, r); while (l + 1 < r) { int m = (l + r) >> 1; if (query(l, m) == ans) r = m; else l = m; } cout << "! " << s[l] << ' ' << s[r]; return 0; }