题意

给一棵 $n$ 个结点的树，树上有一条链 $(u, v)$。$u, v$ 是未知的。
可以询问若干次，每次可以询问一个点集，评测机返回该点集中在 $(u, v)$ 链上的点数。
需要通过询问找出 $u, v$，询问次数限制在 $lim$ 内。

分析

交互题可以先观察数据范围猜测询问次数的大概模样。观察本题数据范围，发现 $lim$ 在 $3 \log n$ 附近。

考虑 $\log n$ 次询问可以干啥，他可以找出一个链上的点。具体操作是二分前缀，每次询问前缀，直到找到一个位置 $p$，满足前缀 $qry (p - 1) = 0$ 且 $qry (p) = 1$，那么 $p$ 就是链上的一点。另外注意到，$p$ 同时是点集中最靠前的链上点。

有了上面这个找点的方法，就能轻松达到 $3 \log n$ 的要求了。方法如下：

1. 找个链上点，记为 $rt$。链 $(u, v)$ 会被 $rt$ 分成两部分。
2. 从 $rt$ DFS 一遍，记录所有点的深度 $dep$。按 $dep$ 降序排序，再找一个点，记为 $x$。那么 $x$ 就是深度最大的链上点了。因此 $x$ 也一定是 $u$ 或者 $v$。
3. 把 $x$ 的祖先全部从点集中去掉，再找一个点 $y$ 。这个点就是链的另一端点了。输出 $x, y$ 即可。

但还有 $2 \log n$ 的做法。方法如下：

1. 以任意点为根 DFS，求出所有点的深度 $dep$ 并按 $dep$ 降序排序。找个点，必然是链端点。
2. 以找出的点为根 DFS，再次求所有点的深度并降序排序。找个点，即为另一端点。

我认为 $2 \log n$ 的做法更加自然。但既然出题人放了 $3 \log n$ 过，那肯定思考的时候要物尽其用。

代码实现

#include <cstdio>
#include <vector>
#include <algorithm>
#include <assert.h>

using vi = std::vector <int>;

const int N = 1e5;

int n;
vi E[N + 5];

int Dep[N + 5];

int R[N + 5];

vi T;

int Qry (vi);
int Get (int);
void DFS (int, int);

int main() {
  scanf ("%d", &n);
  for (int i = 1; i < n; ++i) {
    int u, v;
    scanf ("%d%d", &u, &v);
    E[u].emplace_back (v), E[v].emplace_back (u);
  
  }for (int i = 1; i <= n; ++i) R[i] = i;
  
  DFS (1, 0);
  std::sort (R + 1, R + n + 1, [](int a, int b) {return Dep[a] > Dep[b];});
  int u = R[Get (n)];

  DFS (u, 0);
  std::sort (R + 1, R + n + 1, [](int a, int b) {return Dep[a] > Dep[b];});
  int v = R[Get (n)];

  printf ("! %d %d\n", u, v);
  return 0;

}void DFS (int p, int fp) {
  Dep[p] = Dep[fp] + 1;
  for (int q : E[p]) if (q != fp) DFS (q, p);

}int Get (int rn) {
  int l = 1, r = rn, ans;
  while (l <= r) {
    int mid = (l + r) >> 1;
    for (int i = 1; i <= mid; ++i) T.emplace_back (R[i]);
    if (Qry (T) > 0) ans = mid, r = mid - 1;
    else l = mid + 1;
    T.clear();
  }return ans;

}int Qry (vi A) {
  printf ("%d", (int)A.size());
  for (int i : A) printf (" %d", i);
  putchar ('\n'), fflush (stdout);

  int c;
  scanf ("%d", &c); return c;
}

注意

这题交互器可能有点问题，我写的 $3 \log n$ 做法次数没超过限制但给出的错误信息却说超过了限制，所以可能会 WA 一个点。但 $2 \log n$ 应该是没问题的。