本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 13:55:42

Link

感觉我的做法比较奇怪，但感觉很对。

发现 $N$ 比较小，考虑暴力一点的做法。

考虑如何查找所需次数最少，经典想法就是子树大小接近 $\frac{num}{2}$ ，$num$ 是现在还存在的树的大小（每一次若不存在于子树内则砍掉子树再加回来每一个剩余点的父亲，再砍掉所有叶子，若存在则砍掉除子树之外的部分）。

然后暴力维护这一棵树，如果用 set 来维护则复杂度是单次查询 $O(n\log n)$ 。

为什么这样能较优？考虑极端情况——菊花图，这样的情况下，子树大小是距离 $\frac{num}{2}$ 相当远的。

但是注意到每一次若不在子树中则会向上走一格。而菊花图叶子非常多。这种策略在菊花图时能跑的非常快。

那么在链的情况下呢？容易发现若是链，则 $\frac{num}{2}$ 是非常容易接近的一个数。所以其也能跑的非常快。

我估计一个上界是 $O(\sqrt n)$ 级别的，若有读者能够提出证明欢迎发在评论区。

实现方法则是用 set 维护一个点集，表示这些点可能会存在 mole 。按照dfn排序后倒序处理子树和，类似dp。

然后找到子树和最接近 $\frac{num}{2}$ 且最小的点，对其查询。

若 mole 在其子树内则遍历点集，删掉子树外的点。若不在则删掉子树内的点，再将子树外的点删掉，其父亲加入。

容易发现每一种操作可能涉及的点数量都是 $O(n)$ 。这样单次询问即为 $O(n\log n)$ 。

容易发现删掉子树内/外所有点相当于dfn序列上的一个区间覆盖，可以使用差分预处理，但将父亲插入较难实现。可以找出一个点距离其子树内叶子最远距离，然后考虑一次整体上移造成的影响：删掉所有叶子，加入根的父亲（若有）。删叶子可以通过刚刚所说的预处理子树内距叶子最远距离来实现，加入父亲只会造成 $O(1)$ 级别的影响。这样可以把复杂度优化到 $O(n)$ 。

但是单 $\log$ 的方法在 test 2 ILE 了，线性没调出来，后来写了个 vector 暴力删 过了。有点太逆天了。

其原理与用 set 维护一样，同样是删除与去重。但是由于 vector 删除复杂度高且去重也要手动所以不优。

以下是 $O(n^2)$ 的 vector 暴力删做法代码。

code

const int N=5e3+5;

struct edge{
	int v,nxt;
}e[N<<1];
int head[N],tott;
void add(int u,int v){e[++tott]={v,head[u]},head[u]=tott;}

vector<int> vec;

int dep[N],dfn[N],cnt;
int L[N],R[N];
int fa[N];
void dfs(int u,int faa){
	L[u]=dfn[u]=++cnt;
	dep[u]=dep[faa]+1;
	fa[u]=faa;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==faa)
			continue;
		dfs(v,u);
	}R[u]=cnt;
}

bool cmp(int x,int y){
	return dep[x]==dep[y]?dfn[x]<dfn[y]:dep[x]<dep[y];
}

bool tag[N];
int sum[N];
bool ask(){
	int id=vec.back();
	int num=vec.size()\/2;
	for(int i=vec.size()-1;i>=0;i--){
		int v=vec[i];
		sum[v]++;
		if(abs(sum[v]-num)<abs(sum[id]-num)||
		  (abs(sum[v]-num)==abs(sum[id]-num)&&sum[v]<sum[id]))
			id=v;
		if(tag[fa[v]])
			sum[fa[v]]+=sum[v];
	}
	for(int i:vec)
		sum[i]=0;\/\/清空
	cout<<"? "<<id<<endl;
	int opt=read();
	if(opt){
		for(int i=0;i<vec.size();i++){
			int v=vec[i];
			if(dfn[v]>R[id]||dfn[v]<L[id]){
				tag[v]=0;
				vec.erase(vec.begin()+i);
				i--;
			}
		}
	}else{
		for(int i=0;i<vec.size();i++){
			int v=vec[i];
			if(dfn[v]<=R[id]&&dfn[v]>=L[id]){
				tag[v]=0;
				vec.erase(vec.begin()+i);
				i--;
			}else if(v!=1){
				tag[v]=0;
				tag[fa[v]]=1;
				vec[i]=fa[v];
				if(i>0&&vec[i]==vec[i-1]){\/\/去重，在按照深度及dfn序排序后，若同时将数列中每一个点替换为其父亲，则相同的数字一定出现在连续的一段
					vec.erase(vec.begin()+i);
					i--;
				}
			}
		}
	}
	if(vec.size()==1){
		cout<<"! "<<vec[0]<<endl;
		vector<int> tmp;
		swap(tmp,vec);\/\/清空vector
		return 1;
	}return 0;
}

signed main(){
	signed _T=read();
	while(_T--){
		int n=read();
		for(int i=1;i<n;i++){
			int u=read(),v=read();
			add(u,v),add(v,u);
		}
		dfs(1,0);\/\/预处理
		for(int i=1;i<=n;i++)
			vec.pb(i),tag[i]=1;\/\/tag表示还存在于点集内
		sort(all(vec),cmp);
		while(!ask());
		for(int i=1;i<=n;i++)
			head[i]=tag[i]=0;
		tott=0;
		cnt=0;
	}
	return 0;
}