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;
}