题解：CF1370F2 The Hidden Pair (Hard Version)

本文主要是介绍题解：CF1370F2 The Hidden Pair (Hard Version)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

交互题。 给你一棵 $n$ 个点的树，需要得出树上两个点 $X, Y$ 的位置。你可以向评测机询问一个点集，评测机会回答点集中与 $X, Y$ 距离和最小的点，以及这个距离和。询问不超过 $11$ 次。

思路

询问次数不能超过 $11$ 次，这个数字与 $\log n$ 的值很接近。考虑先对所有 $n$ 个点进行询问，这样就可以得到 $X, Y$ 之间的距离，和一个必定在 $X, Y$ 路径上的点。设这个点为 $r t$ ， $X, Y$ 之间的距离为 $d i s$ 。如果我们以 $r t$ 为树根，那么对于树中深度为 $d e p$ 的点集 ${A\}$ ，且 $d e p$ 大于等于 $X, Y$ 中较小的深度，我们对其进行询问：

如果询问得到的距离和为 $d i s$ ，则表示询问得到的点在 $X, Y$ 的路径上，即 $X, Y$ 中较大的深度大于等于 $d e p$ ；
如果询问得到的距离和大于 $d i s$ ，则表示该深度的点中没有在 $X, Y$ 的路径上的，即 $X, Y$ 中较大深度小于 $d e p$ 。

对于第一种情况询问到的点都可能是 $X, Y$ 中深度较大的点，不妨令 $dep_X\ge dep_Y$ 。考虑二分，区间为 $[\lfloor\cfrac{dis}{2}\rfloor,\min(dis,Dep)]$ ，其中 $De p$ 为最大深度。每一轮都询问一次深度为 $mi d$ 的点集，按照上述两种情况二分，最终可以得到深度较大的 $X$ 。然后我们以 $X$ 为树根，然后询问深度为 $d i s$ 的点集，得到的点即为 $Y$ 。

为什么二分区间上界可以这么取？

感性理解一下，因为我们要处理出 $X, Y$ 较深的一个点，所以深度小于 $d i s (X, Y)$ 的点都不会是那个较深的点。

实现

实现没什么难点，注意每次询问/回答都要 fflush(stdout)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
vector<int> mp[maxn << 1];
void addEdge(int u,int v) {mp[u].push_back(v);
}
vector<int> a[maxn]; int Dep;
void dfs(int u,int fa,int dep) {a[dep].push_back(u);Dep = max(Dep,dep);for (auto v : mp[u]) {if (v == fa) continue;dfs(v,u,dep + 1);}
}
pair<int,int> Query(const vector<int> &ask) {printf("? %d",ask.size());for (auto x : ask) printf(" %d",x);puts(""); fflush(stdout);int x,d;scanf("%d %d",&x,&d);return make_pair(x,d);
}
pair<int,int> Solve(int n,const vector<pair<int,int> > &edge) {for (int i = 1;i <= n;i ++)mp[i].clear();for (int i = 0;i <= Dep;i ++) a[i].clear();Dep = 0;for (auto E : edge) {int u = E.first, v = E.second;addEdge(u,v); addEdge(v,u);}vector<int> ask;for (int i = 1;i <= n;i ++) ask.push_back(i);pair<int,int> res = Query(ask);int rt = res.first, sum = res.second;dfs(rt,0,0);int l = sum >> 1, r = min(Dep,sum);int X = 0;while (l <= r) {int mid = l + r >> 1;res = Query(a[mid]);if (res.second == sum) l = mid + 1, X = res.first;else r = mid - 1;}for (int i = 0;i <= Dep;i ++) a[i].clear();Dep = 0; dfs(X,0,0);return make_pair(X, Query(a[sum]).first);
}
int T,n; char AC_or_WA[maxn];
vector<pair<int,int> > Edge;
int main() {scanf("%d",&T);while (T --) {scanf("%d",&n);Edge.clear();for (int i = 1,u,v;i < n;i ++) {scanf("%d%d",&u,&v);Edge.emplace_back(u,v);}pair<int,int> ans = Solve(n,Edge);printf("! %d %d\n",ans.first,ans.second);fflush(stdout);scanf("%s",AC_or_WA + 1);}return 0;
}