The Hidden Pair (Hard Version)[Div2651F][交互题]

题目

Luogu

思路

首先问所有点，问出这条路径长度和其中一个点
然后再二分问出较深的端点
最后在问出另外一个点
$次数=2+?lo{g}_2(500)?=11$
$flush$ 函数：清空缓冲区用于交互

代码

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int read(){
    int f=0,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define mp make_pair
const int MAXN=100000;
const int INF=0x3f3f3f3f;
int dep[MAXN+5],Max;
vector<int> G[MAXN+5],V[MAXN+5];
void DFS(int u,int fa){
    Max=max(Max,dep[u]);V[dep[u]].push_back(u);for(int i=0;i<(int)G[u].size();i++){
    int v=G[u][i];if(v==fa) continue;dep[v]=dep[u]+1,DFS(v,u);}return ;
}
int rt,Len;
int main(){
    int T=read();while(T--){
    Max=0;int n=read();for(int i=1;i<=n;i++)V[i].clear(),G[i].clear();for(int i=1;i<n;i++){
    int u=read(),v=read();G[u].push_back(v);G[v].push_back(u);}cout<<'?'<<' '<<n;for(int i=1;i<=n;i++)cout<<' '<<i;cout<<endl;rt=read(),Len=read();dep[rt]=0,DFS(rt,0);int L=(Len+1)/2-1,R=min(Len,Max)+1,lst=rt;while(L+1<R){
    int Mid=(L+R)>>1;cout<<'?'<<' '<<V[Mid].size();for(int i=0;i<(int)V[Mid].size();i++)cout<<' '<<V[Mid][i];cout<<endl;int u=read(),l=read();if(l==Len) lst=u,L=Mid;else R=Mid;}for(int i=1;i<=n;i++)V[i].clear();dep[lst]=0,DFS(lst,0);cout<<"? "<<V[Len].size();for(int i=0;i<(int)V[Len].size();i++)cout<<' '<<V[Len][i];cout<<endl;int w=read(),read();printf("! %d %d\n",lst,w);string s;cin>>s;//if(s!="Correct")// exit(0);}return 0;
}