CF1370F2 The Hidden Pair (Hard Version) 题解

题意：

这是一道交互题，且本题有多组数据。

已知一棵 $n$ 个顶点的树（边集已知），其中有两个不同的顶点被暗中做了标记。

你现在需要通过若干次询问，猜出两个被标记顶点的编号。

一次询问的格式为 ? c x1 x2 ... xc，表示向交互库请求关于 $x_1,x_2,\cdots,x_c$ 这 $c(c \le n)$ 个点的信息。

对于一次询问，交互库的返回格式为 x d，表示在询问的集合中，到两个被标记点的距离之和最小的点是 $x$，这个最小值为 $d$。如果有多个最小值点，$x$ 的值可能是其中任意一个。

如果已经知晓答案，请用 ! x y 的格式来输出你的答案，任意顺序均可。在这之后，你会收到一个字符串 Correct 或者 Incorrect，代表你的猜测是否正确。如果收到了 Incorrect，请立即终止程序，否则请继续处理下一组数据。

对于每组数据，请你在不超过 $11$ 次询问之内给出答案。

$1\le t\le 10,~2\le n\le 1000$。

我寻思正解根本不会有 Incorrect ，错解肯定会 Incorrect ，绷不住了。

因为问的节点数没有限制，所以考虑第一次询问所有的节点，把得到的节点和值记为 $\mathrm{root}$ 和 $\rm len$

可以发现，$\mathrm{root}$ 一定位于被标记的两个点 $x \leadsto y$ 的链上，这显然缩小了查询的范围

考虑将 $\mathrm{root}$ 提作根（~~从命名来看早有预谋~~），规定 $d_x \ge d_y$ ，$d$ 表示此时节点的深度，根的深度为 $1$ 。

那么我们用一条水平线 $y=i$ 去截这棵树的话，也就是询问 $d_z=i$ 的所有 $z$ 时

若返回的距离之和等于 $\rm len$ ，那么这个点要么位于 $\mathrm{root} \leadsto x$ 上，要么位于 $\mathrm{root} \leadsto y$ 上。
若返回的距离之和大于 $\rm len$ ，那么这个点 $z$ 肯定有 $d_z < d_x$ ，绝对不可能是 $x,y$ 其中之一。

于是这引导我们去二分这条水平线的深度，并且最终我们会得到 $x$ （除非 $d_x=d_y$ 才可能是 $y$ ）

此时我们把 $x$ 提作根，再询问一遍新的 $d_{\rm len + 1}$ 即可得到 $y$ 。这里加 $1$ 是因为根的深度为 $1$ 。

二分的区间只需要取到 $\left[\left\lceil\frac{\mathrm{len}}{2}\right\rceil,\,\mathrm{len}\right]$ ，那么加上必要的两次询问，总询问数是 $2 + \log_2\left(\frac{n}{2}\right)\le 11$ 次。

注意特判一下 $\mathrm{len}=1$ 的情况，这种情况不会进入二分，为此我调了好久，难绷。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

vector<int> vec[N]; int n, dep[N];
pii query(vector<int> v)
{
    if(v.empty()) return make_pair(0, 0);
    cout << "? " << v.size() << ' ';
    for(int i : v) cout << i << ' ';
    cout << endl; int a, b; cin >> a >> b; return make_pair(a, b);
}
void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    for(int v : vec[u]) if(v != fa) dfs(v, u);
}
vector<int> gen(int d)
{
    static vector<int> res; res.clear();
    for(int i = 1; i <= n; i++)
        if(dep[i] == d) res.push_back(i);
    return res;
}
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) vec[i].clear();
    for(int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v); vec[v].push_back(u);
    }
    static vector<int> tmp; tmp.clear();
    for(int i = 1; i <= n; i++) tmp.push_back(i);
    auto [rt, len] = query(tmp); dfs(rt, 0);
    int l = (len + 1) / 2, r = len, x = 0;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        auto [u, dis] = query(gen(mid + 1));
        if(dis == len) { l = mid; x = u; } else r = mid - 1;
    }
    if(!x) x = query(gen(l + 1)).first;
    dfs(x, 0); int y = query(gen(len + 1)).first;
    cout << "! " << x << ' ' << y << endl;
    static string _; cin >> _; if(_[0] == 'I') exit(0);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}