题解：CF2106G2 Baudelaire (hard version)

由 G1 可知，只要能确定根节点的位置，就能够用 $n$ 次操作获得答案。因此，本题就需要在不超过 $200$ 次的询问中获得根节点的位置。

设当前点为 $u$，与 $u$ 相邻的点组成集合 $S$。若当前询问集合 $Q$ 满足，$Q\subset S$，则可以进行操作：

1. 用 $1$ 操作询问 $Q$，获得答案 $sx$。
2. 进行 $2$ 操作，翻转 $u$。
3. 再次用 $1$ 操作询问 $Q$，获得答案 $sy$。

可以发现，若 $|sx-sy|=2\times |Q|$，则 $Q$ 中不存在 $u$ 的父亲节点。

利用这个性质，可以先找到以 $u$ 为子树的重心 $c$，然后将 $c$ 所有相邻的点加入集合中，通过二分法找到哪一个子结点与根距离最近。具体来说，分为以下情况：

• $c$ 已经不存在相邻点–此时 $c$ 即为所求。
• 询问 $c$ 所有相邻的点且符合以上条件-- $c$ 为所求。
• 剩下的情况就进行二分操作。

综上所述，至多需要约 $n+3\times \lceil \log (n)\rceil$ 次询问之后就能找到根节点。最后进行一次 dfs 并询问即可求出答案。

#include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pii pair <int,int>
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int t,n;
int main ()
{t = read ();while (t--){n = read ();int tot = 0,c = 0;vector <int> ans (n + 1),sz (n + 1),w (n + 1),vis (n + 1,0);vector <vector <int>> ve (n + 1);for (int i = 1;i < n;++i) {int u = read (),v = read ();ve[u].push_back (v);ve[v].push_back (u);}auto query1 = [&] (vector <int> p) -> int{printf ("? 1 %d ",p.size ());for (auto v : p) printf ("%d ",v);puts ("");fflush (stdout);return read ();};auto query2 = [&] (int x) -> void {printf ("? 2 %d\n",x);fflush (stdout);};auto dfs1 = [&] (auto self,int u,int fa) -> void{sz[u] = 1;for (auto v : ve[u]){if (v == fa || vis[v]) continue;self (self,v,u);sz[u] += sz[v];}};auto dfs2 = [&] (auto self,int u,int fa,int pre) -> void{ans[u] = query1 ({u}) - pre;for (auto v : ve[u]){if (v == fa) continue;self (self,v,u,pre + ans[u]);}};auto cen = [&] (auto self,int u,int fa) -> void{sz[u] = 1;w[u] = 0;for (auto v : ve[u]){if (v == fa || vis[v]) continue;self (self,v,u);sz[u] += sz[v];w[u] = max (w[u],sz[v]);}w[u] = max (w[u],tot - sz[u]);if (w[u] <= tot / 2) c = u;};auto ask = [&] (vector <int> p) -> pii{int sx = query1 (p);query2 (c);int sy = query1 (p);return {sx,sy};};auto solve = [&] (auto self,int u) -> int // 找 rt{dfs1 (dfs1,u,u);tot = sz[u];cen (cen,u,u);vis[c] = 1;vector <int> g;for (auto v : ve[c])if (!vis[v]) g.push_back (v);if (g.empty ()) return c;//已经找到 rtint l = 0,r = g.size () - 1,res = 0;auto [sx,sy] = ask (g);if (abs (sx - sy) == 2 * g.size ()) return c;//重心即为 rtwhile (l <= r){int mid = (l + r) >> 1;vector <int> tmp;for (int i = 0;i <= mid;++i) tmp.push_back (g[i]);auto [sx,sy] = ask (tmp);if (abs (sx - sy) == 2 * tmp.size ()) l = mid + 1;else res = mid,r = mid - 1;}return self (self,g[res]);};dfs2 (dfs2,solve (solve,1),0,0);printf ("! ");for (int i = 1;i <= n;++i) printf ("%d ",ans[i]);puts ("");fflush (stdout);}return 0;
}
inline int read ()
{int s = 0;int f = 1;char ch = getchar ();while ((ch < '0' || ch > '9') && ch != EOF){if (ch == '-') f = -1;ch = getchar ();}while (ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar ();}return s * f;
}