题意
给你一颗树，大小为 \(n\)。初始有一颗黑点在树上某个节点，你每次可以查询 \(x\) 表示黑点是否在 \(x\) 的子树内，且若答案为否则黑点会移动到父亲节点上。你需要在 160 次查询内找到黑点当前在哪个节点（不要求求出初始位置）。
\(n\le 5000\)，Easy Ver. 查询次数 300。
分析
由于每次失败的查询（答案为否的查询）会使得黑点上移，考虑设一个阈值 \(B=\sqrt n\)（叫根号分治可能不太准确），那么在 \(B\) 次失败的查询后，如果黑点初始位置和根节点之间的链 \(\le B\)，那么黑点最终会移动到根节点处。
如果令“长链”表示链长 \(>B\) 的链，那么黑点初始在这些“长链”的情况可以通过暴力查询长度恰好为 \(B\) 的链端点完成。如果一次查询是失败的，那么黑点不可能出现在查询点的子树内，那么直接把子树删掉就行。每次删掉的点数量至少是 \(B\) 个，所以这部分总查询次数不超过 \(B\)。
如果这些查询全部都是失败的，那么我们最终会剩下若干条最大深度不超过 \(B\) 的链，直接暴力查询 \(B\) 次叶子，然后返回根节点 1 即可。查询次数 \(2\sqrt n\)。
如果存在一次查询是成功的，那么此时黑点一定在这棵子树内（废话），而且子树深度为 \(B\)。
我们考虑二分出黑点的位置，但是有可能该子树内还存在着多个子树，我们无法确定黑点具体在哪棵子树。此时我们只需要再查询 \(B\) 次叶子，由于子树深度为 \(B\)，那么查询后黑点一定会在根节点到子树根节点的这条链上，那么我们有了具体上下界，就可以二分了。查询次数 \(2\sqrt n+\log n\)。
关于二分：我们二分的是二分前黑点的位置，而不是二分时黑点当前的位置，考虑设一个变量 \(cnt\) 代表二分时进行了多少次失败的查询，即黑点上移的距离，那么每次二分出 \(mid\) 实际上查询的是 \(mid\) 的 \(cnt\) 级祖先，也就是查询黑点二分前是不是在 \(mid\) 的子树里。
实现细节：最开始查询的时候，每进行一次失败的查询，需要删掉一整棵子树，然后求出新的长度为 \(B\) 的链的端点。这部分实际上可以 \(O(n)\) 暴力 dfs、暴力删除，由于查询次数只有 \(\sqrt n\) 次，所以时间复杂度是 \(O(Tn\sqrt n)\) 的。同理，二分时由于要查询某点 \(k\) 级祖先，实际上也可以暴力。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
typedef long long i64;
using pii=pair<int,int>;
bool greating(int x,int y){return x>y;}
bool greatingll(long long x,long long y){return x>y;}
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=5e3+5,maxm=4e5+5,inf=0x3f3f3f3f,B=71;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n;
vector<int>G[maxn];
int ask(int x){
cout<<"? "<<x<<endl;
int y=rd();return y;
}
void answer(int x){
cout<<"! "<<x<<endl;
}
bool vis[maxn];
int dep[maxn],mxdep[maxn];
int fa[maxn];
int a[maxn],m;
int leaf;
void dfs(int x,int y){
dep[x]=dep[y]+1,fa[x]=y,mxdep[x]=dep[x];
bool ok=1;
for(int u:G[x])if(u!=y&&!vis[u])dfs(u,x),mxdep[x]=max(mxdep[x],mxdep[u]),ok=0;
if(ok)leaf=x;
}
void del(int x,int y){
vis[x]=1;
for(int u:G[x])if(u!=y&&!vis[u])del(u,x);
}
void init(){
m=0;
rep(i,1,n)G[i].clear(),vis[i]=0;
}
int getfa(int x,int k){
if(!k||!x)return x;
return getfa(fa[x],k-1);
}
void solve_the_problem(){
n=rd(),init();
rep(i,2,n){
int x=rd(),y=rd();
G[x].emplace_back(y),G[y].emplace_back(x);
}
bool ok=0;
int rt=0;
rep(_,1,B){
dfs(1,0);
int p=-1;
rep(i,2,n)if(!vis[i]&&mxdep[i]-dep[i]==B){p=i;break;}
if(p==-1)break;
int r=ask(p);
if(r==1){
rt=p,ok=1;
break;
}
del(p,fa[p]);
}
if(!ok){
rep(i,1,B){
int r=ask(leaf);
if(r==1)return answer(leaf);
}
return answer(1);
}
int p=rt;
while(p)a[++m]=p,p=fa[p];
reverse(a+1,a+m+1);
rep(i,1,B){
int r=ask(leaf);
if(r)return answer(leaf);
}
int l=1,r=m,res=-1,cnt=0;
while(l<=r){
int mid=l+r>>1;
int an=getfa(a[mid],cnt);
// printf("Debug: l=%d,r=%d,mid=%d\n",l,r,mid);
if(!an){
l=mid+1,res=mid;
continue;
}
int re=ask(an);
if(re)l=mid+1,res=mid;
else r=mid-1,++cnt;
}
assert(res!=-1);
int an=getfa(a[res],cnt);
if(!an)an=1;
answer(an);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=rd();
while(_--)solve_the_problem();
}
/*
1
10
1 2
1 3
1 4
4 5
5 6
6 7
7 8
8 9
9 10
*/